Задача A. Геологическое исследование

Компания <<КазЖелУгЗол>> готовит крупномаштабный-план по добыче полезных ископаемых. Компания наняла геолога Асем для исследования $n$ месторождений. Для $i$-го месторождения из списка компании Асем определила оценку $c_i$ -- ожидаемый объем добычи. Поскольку необходимо построить склад возле месторождений, было решено что работа по добыче будет проходить в последовательных месторождениях из списка. Тем временем отдел финансовой аналитики компании разработал оценку плана $f_k(l, r)$ равную $k$-му по убыванию значению среди чисел $c_l, c_{l + 1}, ..., c_r$. Если в отрезке от $l$ до $r$ менее $k$ чисел, значение $f_k(l, r)$ равно нулю. Директору компании стало интересно, чему равно значение $S = \sum_{1 <= l <= r <= n}f_k(l, r)$ для какого то $k$ (суммарное значение $f_k(l, r)$ по всем отрезкам $(l, r)$). Асем уверенна в корректности значений $c_i$. Помогите написать программу для эффективного подсчета значения $S$. В первой строке даны два числа $n$ и $k$($1 <= n <= 10^5, 1 <= k <= min(n, 500)$). Во второй строке даны $n$ чисел $c_1, c_2, ..., c_n$ -- оценки месторождений($1 <= c_i <= 10^7$). Выведите одно число $S$. Данная задача содержит $9$ подзадач, в которых выполняются следующие ограничения:

1. Тесты из условия. Оценивается в $0$ баллов.
2. $n <= 100$. Оценивается в $11$ баллов.
3. $n <= 5000$, $k = 1$. Оценивается в $11$ баллов.
4. $n <= 5000$. Оценивается в $12$ баллов.
5. $n <= 10^5$, $k = 1$. Оценивается в $15$ балла.
6. $n <= 10^5$, $k = 2$. Оценивается в $10$ баллов.
7. $n <= 10^5$, $a_i <= 2$. Оценивается в $9$ баллов.
8. $n <= 10^5$, $a_i <= 500$. Оценивается в $14$ баллов.
9. Исходные условия задачи. Оценивается в $18$ баллов.

Вход

5 3
1 2 3 2 1

Ответ

10

Вход

7 4
1 1 1 1 1 1 1

Ответ

10

В первом примере $f_3(1, 3) = f_3(3, 5)= 1, f_3(1, 4) = f_3(1, 5) = f_3(2, 4) = f_3(2, 5) = 2$.

Задача B. Витя - черепашка-ниндзя

Витя готовится стать членом команды нового поколения черепашек-ниндзя. Ему осталось пройти самое важное испытание - решить задачу Донателло. Донателло дал Вите таблицу состоящую из $n$ строк и $m$ столбцов. В каждой клетке таблицы написано целое число. Изначально, на клетке в левом верхнем углу таблицы находится фишка. Фишку можно двигать либо на одну клетку вниз либо на одну клетку вправо и только если на соответствующей стороне существует другая клетка. Фишку двигают пока она не окажется на клетке в правом нижнем углу таблицы. Результатом пути называется сумма чисел на клетках по которым прошла фишка (включая начальную и последнюю клетку). Вите нужно найти путь с максимальным результатом. Узнав об этом испытании, Леонардо решил что Витя очень легко справится с таким заданием (при его то потенциале). Поэтому, он решил усложнить задачу. На этот раз, перед тем как двигать фишку, Витя может попросить Леонардо сделать некоторое (возможно нулевое) количество вертикальных и горизонтальных разрезов на таблице своими катанами. Резать можно только по краям клеток и можно считать что катаны Леонардо всегда длиннее сторон таблицы (то есть таблица режется от края до края). В итоге, таблица разделяется на секции. Теперь фишка стоит на левой верхней секции и может двигаться на секцию вниз или на секцию вправо пока не окажется на правой нижней секции. Результатом такого пути называется сумма чисел на клетках секций по которым прошла фишка (включая начальную и последнюю секцию). Помогите Вите разрезать таблицу и найти путь так, чтобы максимизировать результат. В первой строке даны два целых числа $n$ и $m$ ($1 <= n <= 1000$, $1 <= m <= 50$). В следующих $n$ строках даны по $m$ целых чисел -- $j$-тое число на $i$-той строке $a_{i, j}$ ($-10^{9} <= a_{i, j} <= 10^9$) является числом на клетке в $i$-той строке и $j$-том столбце таблицы. Выведите одно целое число -- максимальный результат пути которого можно достичь, после совершения некоторого (возможно нулевого) количества разрезов на таблице. Данная задача содержит $8$ подзадач, в которых выполняются следующие ограничения:

1. Тесты из условия. Оценивается в $0$ баллов.
2. $a_{i, j} > 0$. Оценивается в $5$ баллов.
3. $a_{i, j} < 0$. Оценивается в $12$ баллов.
4. $n = 2$. Оценивается в $10$ баллов.
5. $n, m <= 10$. Оценивается в $10$ баллов.
6. $n, m <= 40$. Оценивается в $20$ баллов.
7. $n <= 100$, $m <= 50$. Оценивается в $21$ балл.
8. Исходные условия задачи. Оценивается в $22$ балла.

Вход

2 2
2000 600
0 4

Ответ

2604

Вход

4 5
4 23 -10 -2 3
0 1 7 -3 0
2 3 -3 30 1
4 -17 8 0 5

Ответ

78

Пояснение ко второму примеру.

Задача C. Выборы в Массивтобе

В городе Массивтобе проводятся очередные выборы акима. Массивтобе -- современный город имеющий систему дорог в виде дерева. В нем есть $n$ домов соединенных $n - 1$ двусторонними дорогами так, что из каждого дома можно добраться до всех остальных передвигаясь по этим дорогам. Айбар — начинающий блогер, который хочет осветить выборы. Он решил снять видео социального опроса в котором он собирается идти по простому пути в городе и спрашивать за кого голосует жители каждого дома. Путь считается простым если он проходит по каждой вершине не более одного раза. Айбар знает, что видео не наберет много просмотров если в нем не будет доминантного кандидата. Кандидат считается доминантным если более половины опрошенных в видео голосуют за него. Всего есть $n$ кандидатов с номерами от $1$ до $n$. Вам дан список $v_1$, $v_2$, \dots, $v_n$, где значение $v_i$ означает, за кого голосуют жители $i$-го дома. Чтобы произвести как можно больше контента Айбар просит вас посчитать сколько есть различных путей в Массивтобе с доминантным кандидатом. Путь идущий из вершины $v$ в вершину $u$, считается таким же как и путь из $u$ в $v$. В первой строке находится одно целое число $n$ ($1 <= n <= 77777$). Во второй строке находятся $n$ целых чисел $v_1$, $v_2$, \dots, $v_n$ ($1 <= v_i <= n$). В каждом из следующих $n - 1$ строк находятся два целых числа $a$ и $b$ ($1 <= a, b <= n$, $a \neq b$) означающие существование дороги между домами $a$ и $b$. Выведите одно целое число — количество различных путей с доминантным кандидатом. Данная задача содержит $9$ подзадач, в которых выполняются следующие ограничения:

1. Примеры из условия. Оценивается в $0$ баллов.
2. $n <= 100$. Гарантируется, что $a_i=i$, $b_i=i+1$ для всех $i$ ($1 <= i < n$). Оценивается в $6$ баллов.
3. $n <= 2000$. Гарантируется, что $a_i=i$, $b_i=i+1$ для всех $i$ ($1 <= i < n$). Оценивается в $7$ баллов.
4. $n <= 2000$. Оценивается в $8$ баллов.
5. Гарантируется, что $a_i=1$, $b_i=i+1$ для всех $i$ ($1 <= i < n$). Оценивается в $10$ баллов.
6. $v_i <= 100$. Гарантируется, что $a_i=i$, $b_i=i+1$ для всех $i$ ($1 <= i < n$). Оценивается в $9$ баллов.
7. Гарантируется, что $a_i=i$, $b_i=i+1$ для всех $i$ ($1 <= i < n$). Оценивается в $13$ баллов.
8. $v_i <= 100$. Оценивается в $12$ баллов.
9. Исходные условия задачи. Оценивается в $35$ баллов.

Вход

5
1 2 1 2 1
1 2
1 3
1 4
1 5

Ответ

13

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

В одном ряду последовательно расположили $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

Задача B. AB

$N$ школьников из классов А и Б выстроены в ряд. $i$-й школьник в ряду сказал число $c_i$ -- сколько школьников не с его класса стоят левее в ряду. Вам дан перемешанный массив $c$. Восстановите любое возможное изначальное расположение учеников. В первой строке находится одно целое число $N(1 <= N <= 1.5\cdot 10^6)$. Во второй строке находятся $N$ целых числа $x_1,x_2,...,x_N(0 <= x_i <= N)$ — перемешанный массив $c$. Выведите изначальное расположение учеников в виде строки длины $N$ ---состоящей из символов $a$ и $b$. Гарантируется, что существует хотя бы одна такая строка. Если есть несколько ответов, выведите любое из них. Данная задача содержит $9$ подзадач, в которых выполняются следующие ограничения:

1. Примеры из условия. Оценивается в $0$ баллов.
2. $N <= 10^5$. Гарантируется, что существует ответ при которым нет не одного ученика с B класса. Оценивается в $6$ баллов.
3. $N <= 20$. Оценивается в $10$ баллов.
4. $N <= 10^5$. Гарантируется, что существует ответ при которым есть не более 2 ученика с B класса. Оценивается в $8$ баллов.
5. $N <= 10^5$. Гарантируется, что существует строка, что полученный массив для этой строки $c$ будет равен массиву $x$ без перемешивание. Оценивается в $14$ баллов.
6. $N <= 40$. Оценивается в $13$ баллов.
7. $N <= 2000$. Оценивается в $10$ баллов.
8. $N <= 300000$. Оценивается в $27$ баллов.
9. $N <= 1500000$. Оценивается в $12$ баллов.

Вход

4
1 0 2 0

Ответ

bbab

Вход

5
0 0 2 1 3

Ответ

bbaba

Если $bbab$ изначальное расположение школьников, то тогда $c_1 = 0, c_2 = 0, c_3 = 2, c_4 = 1$. Перемешав можно получить массив [1,0,2,0].

Задача C. Марафон Канто

Скоро лето, Есмахан решил, что пора начать бегать по утрам в своем городе Канто. Город Канто представляет собой $n$ перекрестков соединённых $n - 1$ дорогой, где от любого перекрестка можно добраться до любого другого перекрестка двигаясь по дорогам. В планах было начать бегать с воскресенья, однако в этот же день был назначен городской ежегодный веломарафон Канто. Определим маршрут $(a,b)$, что $a < b$, множеством дорог, которые лежат на кратчайшем пути между стартовым перекрестком $a$ и конечным перекрестком $b$. Длиной маршрута $(a,b)$ будем называть количество дорог по которым он проходит. Есмахан не хочет бегать по занятым дорогам веломарафона во время пробежки. На вход дается $n$ количество перекрёстков в городе Канто. Далее дается $n - 1$ дорога соединяющая два перекрестка. Гарантируется, что дается дороги таким образом, что от любого перекрестка можно добраться до любого другого перекрестка переходя только по дорогам. После дается $q$ количество запросов на которые вы должны ответить. Запросы даются двух видов:

1. $x$ $y$, в нем вы должны ответить длиной самого длинного маршрута если веломарафон будет проходить через маршрут $(x, y)$.
2. $k$, в нем должны ответить количеством различных маршрутов $(x, y)$, что Есмахан выберет маршрут длиной $k$.

Выведите ответ на каждый запрос. Поэтому хочет выяснить длину самого длинного маршрута $(u, v)$ который будет проходить по свободным дорогам от веломарафона маршрутом $(x, y)$, чтобы его пробежка была максимальна. Так же, Есмахан хочет выяснить сколько возможных маршрутов $(x, y)$ веломарафона возможно, что его пробежке будет длины $k$? Первая строка содержит одно целое число $n$ ($2 <= n <= 5*10^5$), обозначающее количество перекрестков в городе Канто. В каждой из следующих $n-1$ строк содержится описание дорог: два целых числа $u$ и $v$ $(1 <= v,u <= n, u \ne v)$. Следующая строка содержит одно целое число $q$ ($1 <= q <= 5*10^5$), обозначающее количество запросов. Следующие $q$ строк содержат описания запросов. Каждый запрос задан в одном из следующих форматов в зависимости от типа запроса: $1$ $x$ $y$ $(1 <= x < y <= n)$ для запросов первого типа. $2$ $k$ $(0 <= k <= n - 1$) для запросов второго типа. Для каждого запроса выведите ответ на него. Данная задача содержит $10$ подзадач, в которых выполняются следующие ограничения:

1. Примеры из условия. Оценивается в $0$ баллов.
2. $n <= 1000$. Гарантируется, что $u_i=i$, $v_i=i+1$ для всех $i$ ($1 <= i < n$). Оценивается в $8$ баллов.
3. Гарантируется, что $u_i=i$, $v_i=i+1$ для всех $i$ ($1 <= i < n$). Оценивается в $10$ баллов.
4. $n, q <= 500$. Оценивается в $9$ баллов.
5. $n, q <= 3000$. Оценивается в $11$ баллов.
6. Гарантируется, что все запросы 1-типа и $x_i = 1$ для всех $i$ ($1 <= i <= q$). Оценивается в $12$ баллов.
7. Гарантируется, что все запросы 1-типа. Оценивается в $12$ баллов.
8. $q <= 10$. Оценивается в $11$ баллов.
9. $u_i=i+1, v_i=\lfloor \frac{i+1}{2} \rfloor$ для всех $i$ $(1 <= i < n$). Оценивается в $10$ баллов.
10. Исходные условия задачи. Оценивается в $17$ баллов.

Вход

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

Ответ

4
2
2
6
5
12

В первом запросе следущие четыре веломаршрута заставят Есмахана выбрать маршрут длины 3: (1, 3), (1, 5), (3, 6), (5, 6). Во втором запросе два самых длинных маршрутов длины 2: (2, 5) и (4, 8). В третьем запросе один самый длинный маршрут длины 2: (2, 5). В четвертом запросе следущие шесть веломаршрутов заставят Есмахана выбрать маршрут длины 4: (2, 4), (2, 7), (2, 8), (4, 7), (4, 8), (7, 8). В пятом запросе один самый длинный маршрут длинны 5: (6, 8). В шестом запросе ответ 12.