Автор задачи: Мария Жогова, разработчик: Константин Бац
Для простоты будем называть беременных женщин, пожилых людей и пассажиров с детьми особенными пассажирами. Заметим, что если все времена приходов особенных пассажиров ограничены сверху, то последний пришедший найдет себе сидячее место не позже, чем в $$$2 \cdot 10^5$$$. Действительно, так как особенных пассажиров не больше $$$10^5$$$, всем им когда-то найдется место, а $$$a_i \leqslant 10^5$$$.
Сгруппируем всех обычных пассажиров по равным $$$a_i$$$. Для каждой такой группы предподсчитаем моменты $$$t_j$$$, когда пассажиры из этой группы будут отвлекаться от телефонов. По сказанному выше, нас интересуют $$$t_j\leqslant 2 \cdot 10^5$$$. Отсортируем все $$$t_j$$$ по возрастанию и получим последовательность моментов, когда пассажиры из какой-то группы отвлекаются от телефонов.
По условию, если хотя бы один пассажир из группы встал, то все остальные тоже уступили свое место. Поэтому будем для каждой группы хранить флаг: встали пассажиры из этой группы, или нет.
Для решения задачи воспользуемся методом двух указателей: один указатель будет на первом особенном пассажире, который еще не вошел, а второй на моменте, когда обычные пассажиры из какой-то группы отрываются от телефонов. Из двух событий выберем то, которое произойдет раньше, или вход особого пассажира при равенстве времени.
Предположим, вошел особый пассажир. Проверим, если ли ранее освобожденное место: если есть, займем его, иначе добавим пассажира в очередь ожидающих свободного места.
Если же очередная группа обычных пассажиров отвлекается от телефонов, то:
Так как общее количество делителей всех целых чисел от $$$1$$$ до $$$k$$$ равно $$$\dfrac{k}{1} + \dfrac{k}{2} + \dfrac{k}{3} + \dots + \dfrac{k}{k} = \mathcal{O}(k \log k)$$$, то на предподсчет всех $$$t_j$$$ уйдет $$$\mathcal{O}(A \log A)$$$ времени, где $$$A = 2 \cdot 10^5$$$.
Тогда общее время работы решения — $$$\mathcal{O} \left(m + A \log A\right)$$$.