Всем привет!

Хотелось бы уточнить, по поводу времени работы программы одного решения.

Речь пойдёт о задаче: 2063B - Обновление подпоследовательности.

Рассматриваемое решение: 302415890.

Если в кратце, то нам дан масив $$$n$$$ и границы $$$l$$$, $$$r$$$. Нужно минимизировать сумму на этом отрезке, посредством одной операции вида:

• Выбрать любую подпоследовательность из массива и развернуть её.

Часть предлагаемого решения:

• Мы берём все элементы до $$$l$$$, сортируем по неубыванию.

• Берём все элементы от $$$l$$$ до $$$r$$$, сортируем по невозврастанию

• Далее мы сравниваем от все элементы до $$$l$$$ (от минимума) c элементами от $$$l$$$ до $$$r$$$ (от максимума)

• Если элемент 'до $$$l$$$' меньше элемента 'от $$$l$$$ до $$$r$$$' мы удаляем его из vector посредством lt.erase(lt.begin())

for(int i=0;i<q.size();i++){
    if(lt.size()>0 && lt[0]<q[i]){
         s1-=q[i];
         s1+=lt[0];
         lt.erase(lt.begin());
    }
}

Ограничения в задаче таковы, что $$$n <= 10^5$$$, то есть, сделав тест с числами от $$$1$$$ до $$$100 000$$$ и границами $$$l = 50 000, r = 100 000$$$:

1
100000 50000 100000
1 2 3 4 ... 100000

Мы должны будем удалить из массива $$$50000$$$ элементов с помощью lt.erase(lt.begin()).

Насколько мне известно, erase работает за линейное время и при удалении элемента из начала массива сдвигает все элементы влево. Таким образом итоговое решение должно выполнять по крайней мере $$$\sum_{i=1}^{50 000} i = 1 250 025 000 $$$ операций (не считая всего остального). И такое решение не должно заходить по моим подсчётам (」°ロ°)」

Моя попытка взлома, если нужно: тык

Подскажите пожалуйста, почему так происходит, где я ошибся, может не знаю про какие-либо оптимизации или особенности работы программы)

P.S.: может я не разбираюсь, но предусмотрен ли функционал для того, чтобы писать с новой строки без пробела (пустой строки) от предыдущей)?