Дорожный патруль

Заметим, что оптимальными значениями для ограничения являются числа $$$a_i$$$, поэтому таких значений не более $$$n$$$. Давайте отсортируем машины по убыванию скорости и будем при добавлении очередной машины заново считать ответ.

При $$$t \geqslant 3000$$$ заметим, что мы остановим не более $$$O(\frac{n}{t})$$$ машин, поэтому мы можем сложить позиции всех машин со скоростью больше данной в set, а следующую, которую нужно остановить, искать с помощью lower bound. Такое решение работает за $$$O(n \frac{n}{t} \log n)$$$.

В общем случае, давайте разделим весь массив на блоки по $$$\sqrt{n}$$$, для каждого элемента будем пересчитывать первую машину вне его блока, которую мы остановим после него. Аналогично будем пересчитывать сумму $$$a_i$$$ всех машин между данной и следующей из другого блока, а также число таких машин. Заметим, что при добавлении новой машины мы можем пересчитать весь блок за его размер (т.е. за $$$O(\sqrt{n})$$$) проходом справа налево.

Осталось уметь пересчитывать ответ, используя такую структуру. Достаточно поддерживать первую машину, которую мы остановим, после чего, начиная с неё, переходить к машинам в следующих блоках, с помощью того, что мы насчитали. При таком процессе нужно поддерживать число остановленных машин и сумму их скоростей, после чего для данного ограничения скорости можно восстановить ответ. Такое решение работает за $$$O(n \sqrt{n})$$$.