4-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура

Задача A. Башни

Ограничение по времени:

1.5 секунд

Ограничение по памяти:

256 мегабайт

В одном ряду последовательно расположили $n$ башен из кубиков. $i$-я башня состоит из $a_i$ кубиков, которые выставлены вертикально друг над другом. Гарантируется, что все башни состоят из не более чем $k$ кубиков. Все кубики подчиняются закону гравитации — они падают вниз до тех пор пока не коснутся пола или верхней стороны другого кубика. А также в задаче есть слои льда. Если на высоте $y$ есть лед, это означает что никакой кубик не может упасть с высоты $y+1$ на $y$ пока этот лед не исчезнет. BThero последовательно дает вам $q$ запросов трех видов.

1. Вам дается одно единственное число $y$, и на высоте $y$ появляется слой льда.
2. Вам дается одно единственное число $y$, и на высоте $y$ исчезает слой льда.
3. Вам дается одно единственное число $y$, и на высоте $y$ устанавливается новый лазер. Гарантируется, что на этой высоте ранее еще не был установлен никакой лазер. Номером этого лазера будет являться минимальное еще не занятое положительное число. Лазер можно представить как бесконечную горизонтальную линию на высоте $y$ и он будет уничтожать все кубики и слои льда которые его касаются. Может быть такое, что лазер уничтожил кубик, а сверху по закону гравитации на его место упал другой кубик. Тогда тот кубик тоже уничтожится, и процесс может повториться снова.

Обозначим суммарное количество установленных лазеров как $m$. После всех запросов выведите количество уничтоженных кубиков для каждого лазера.

Формат входного файла

В первой строке входного файла даны три целых числа $n$, $q$ и $k$ — количество башен, количество запросов и ограничение на количество кубиков в башнях ($1 <= n, q <= 300000$, $1 <= k <= 10^9$). Во второй строке даны $n$ целых чисел $a_1$, \dots, $a_n$ ($1 <= a_i <= k$). В последующих $q$ строках даны все запросы в формате $t_i$, $y_i$ — тип $i$-го запроса и число, связанное с этим запросом ($1 <= t_i <= 3$, $1 <= y_i <= k$).

Формат выходного файла

Выведите $m$ целых чисел $c_1$, \dots, $c_m$ разделенные пробелами — количество уничтоженных клеток для каждого лазера. Гарантируется, что $m > 0$.

Система оценки

Данная задача содержит $7$ подзадач.

1. Примеры из условия. Оценивается в $0$ баллов.
2. $n, k, q <= 100$. Оценивается в $15$ баллов.
3. $n, k, q <= 5000$, $t_i = 3$ для всех $1 <= i <= q$. Оценивается в $8$ баллов.
4. $n, k, q <= 5000$. Оценивается в $13$ баллов.
5. $k <= 300000$. Оценивается в $19$ баллов.
6. $t_i \neq 2$ для всех $1 <= i <= q$. Оценивается в $16$ баллов.
7. Исходные условия задачи. Оценивается в $29$ баллов.

Пример:

Вход

4 5 8
5 2 4 7
1 5
3 2
3 3
2 5
3 1

Ответ

10 4 4

( Temirlan Baibolov )