Петух Хей-Хей и камни

Автор задачи и разработчик: Даниил Голов

Заметим следующий факт: относительный порядок петухов никогда не меняется. Действительно, для петухов, движущихся в одном направлении, это очевидно, а для движущихся в разном известно, что они движутся к общей цели — первый из них, достигший цели, достигнет ее раньше, чем встретится со вторым, значит они не успеют поменяться местами.

А в таком случае задачу можно переформулировать следующим образом: есть $$$n$$$ позиций петухов $$$a_i$$$ и $$$m$$$ камней. Камни надо обрабатывать в порядке уменьшения их $$$k_i$$$, и для очередного камня на позиции $$$b$$$:

Поиск очередного камня можно выполнять за $$$\mathcal{O}(1)$$$ — достаточно их заранее отсортировать по $$$k_i$$$. Для выполнения оставшихся операций достаточно поддерживать декартово дерево всех позиций петухов. Чтобы найти $$$d$$$, достаточно сделать $$$\mathtt{split}(b)$$$ и рассмотреть крайние элементы двух полученных деревьев. Операции увеличения или уменьшения позиций петухов на $$$d$$$ — это просто отложенные массовые операции, которые можно применять к полученным двум деревьям за $$$\mathcal{O}(1)$$$.

Итого решение работает за $$$\mathcal{O}((m + n) \log(n + m))$$$.