Автор задачи и разработчик: Владислав Власов

Задачу можно представить следующим образом. Есть $$$a_1 + \ldots + a_n$$$ дней, и из этого ряда выбирается каждый $$$k$$$-й день. Требуется понять, в каких из $$$n$$$ блоков хотя бы один день выбран. Можно сразу заметить, что если $$$a_i \geqslant k$$$, то в $$$i$$$-м блоке гарантированно будет выбран хотя бы один день. Дальше от решения подгрупп до полного решения надо сделать несколько шагов.

Для решения второй подгруппы нужно было только понять, будут ли решаться контесты с $$$a_i = 1$$$, потому что для всех остальных автоматически ответ «да». Но в таком случае это зависит только от того, в четный или нечетный день этот контест проходит. Можно пройтись по массиву $$$a$$$ и посчитать префиксные суммы, после чего проверить четность дней, в которые проходят однодневные контесты.

Ограничения третьей подруппы позволяли в явном виде выписать какой контест в какой из $$$a_1 + \ldots + a_n$$$ проходит, и перебрать все дни, номера которых делятся на $$$k$$$. Это решение работает за $$$\mathcal{O}(a_1 + \ldots + a_n)$$$.

Четвертая подгруппа совмещает две предыдущие идеи. Выписать все дни уже не получится, но можно посчитать префиксные суммы массива $$$a$$$, после чего перебрать все дни, делящиеся на $$$k$$$ (которых будет не больше трех), и для каждого понять, какая лабораторная в этот день проходит.

Полное решение не сильно отличается от предыдущей идеи. Посчитав префиксные суммы массива $$$a$$$, можно понять в какие дни какая лабораторная проходит, после чего останется только для каждой лабораторной понять, есть ли в ее интервале день, делящийся на $$$k$$$. Это можно сделать за $$$\mathcal{O}(1)$$$ — если лабораторная идет в дни с $$$l$$$-го по $$$r$$$-й, то в эти дни есть день, делящийся на $$$k$$$, если $$$r - (r \bmod k) \geqslant l$$$, то есть последний делящийся на $$$k$$$ день перед $$$r$$$-м лежит не раньше $$$l$$$-го.