ARTpositive's blog

By ARTpositive, 4 weeks ago, In Russian

Всем привет!

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

Речь пойдёт о задаче: 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=1250025000 операций (не считая всего остального). И такое решение не должно заходить по моим подсчётам (」°ロ°)」

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

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

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

  • Vote: I like it
  • +23
  • Vote: I do not like it