Всем привет!
Хотелось бы уточнить, по поводу времени работы программы одного решения.
Речь пойдёт о задаче: 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<=105, то есть, сделав тест с числами от 1 до 100000 и границами l=50000,r=100000:
1
100000 50000 100000
1 2 3 4 ... 100000
Мы должны будем удалить из массива 50000 элементов с помощью lt.erase(lt.begin())
.
Насколько мне известно, erase
работает за линейное время и при удалении элемента из начала массива сдвигает все элементы влево. Таким образом итоговое решение должно выполнять по крайней мере ∑50000i=1i=1 250 025 000 операций (не считая всего остального). И такое решение не должно заходить по моим подсчётам (」°ロ°)」
Моя попытка взлома, если нужно: тык
Подскажите пожалуйста, почему так происходит, где я ошибся, может не знаю про какие-либо оптимизации или особенности работы программы)
P.S.: может я не разбираюсь, но предусмотрен ли функционал для того, чтобы писать с новой строки без пробела (пустой строки) от предыдущей, когда пишешь пост на codeforces)?