@ChastIOtvaga

Почему код не проходит по тайм лимиту?

Не проходит по тайм лимиту:

Формат входа. Первая строка содержит исходную строку S, вторая — число запросов q. Каждая из последующих q строк задаёт запрос тройкой чисел i, j, k и означает следующее: вырезать подстроку S[i..j] (где i и j индексируются с нуля) и вставить её после k-го символа оставшейся строки (где k индексируется с единицы), при этом если k = 0, то вставить вырезанный кусок надо в начало.
Формат выхода. Выведите полученную (после всех q запросов) строку.
Ограничения. S содержит только буквы латинского алфавита. 1 ≤
|S| ≤ 300 000; 1 ≤ q ≤ 100 000; 0 ≤ i ≤ j ≤ n−1; 0 ≤ k ≤ n−(j−i+1).

#include <iostream>
#include <string>
using namespace std;

int main() {
    string S;
    int q;
    cin >> S >> q;
    S.reserve(S.length() + q); // резервируем память для добавления подстрок
    for (int i = 0; i < q; i++) {
        int i_pos, j_pos, k_pos;
        cin >> i_pos >> j_pos >> k_pos;
        string sub = S.substr(i_pos, j_pos - i_pos + 1);
        S.erase(i_pos, j_pos - i_pos + 1);
        if (k_pos == 0) {
            S = sub + S;
        } else if (k_pos <= S.length()) {
            S.insert(k_pos, sub);
        } else {
            S += sub;
        }
    }
    cout << S << endl;
    return 0;
}
  • Вопрос задан
  • 183 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
С такими ограничениями надо менять алгоритм. У вас наивная реализация за O(nq). А надо реализовывать rope за O(q log n).

Какими-то стандартными контейнерами это не сделать вообще никак.

Советую реализовывать декартово дерево по неявному ключу. Это самая простая реализация будет. Ну, а дальше вам надо будет это дерево разрезать на три части двумя Split, две крайние объеденить, разрезать это в новом месте и слить уже 3 части с вырезанным куском в середине.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
Adamos
@Adamos
Функции работы со строками будут постоянно выделять память, это дорогая операция.
Ваша задача, в сущности, не требует такого выделения.
Достаточно завести два массива длиной в строку, заполнить первый числами по порядку и при каждой итерации заполнять другой перестановкой, а потом менять их местами.
В конце составить строку по получившимся индексам символов.
Это будет однозначно быстрее за счет стабильной памяти (в сущности, вообще не будет обращаться к памяти, все будет крутиться в кэше процессора).
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы