Aidos Nurmash


Задача №1. 

Задача B. Охрана природы

Ограничение по времени:
2 секунды
Ограничение по памяти:
512 мегабайт

Темирулан — активист охраны природы и защиты животных округа Каспий. Недавно во время прогулки по родному краю он обнаружил редкое растения типа ЖранУ. Растения ЖранУ являются особенными. Они растут только в тени под большими, старыми деревьями. Темирулан проверил $n$ подряд идущих деревьев, и для каждого из них узнал можно ли под ним посадить растение ЖранУ. Темирулану растение ЖранУ сильно понравилось, и он решил, что каждый год в течении следующих $q$ лет будет делать посадку этого растение. При посадке растения он выбирает некоторое количество подряд идущих деревьев от $l$ до $r$, и под каждым деревом делает посадку растение ЖранУ если можно посадить. После посадки растения их обязательно нужно полить, каждый год Темирулан поливает все растения посаженные в этот год. Для поливки растения Темирулан взял с собой ведро размера $k$, которым можно полить все растения ЖранУ которые растут под $k$ подряд идущими деревьями. Темирулан хочет полить каждое посаженное растение хотя бы один раз. Какое минимальное количество ведер воды для поливки всех новых посаженных растении? Обратите внимание, каждый год Темирулан поливает растения не учитывая предыдущий год.
Формат входного файла
Первая строка входных данных содержит два целых числа $n$ и $t$ $(1 \le n \le 2\cdot10^5, 0 \le t \le 1)$ — количество деревьев и константное число для чтения входных данных. Далее следующие $n$ чисел описывает $i$-е дерево — если $i$-е число 0, то нельзя посадить растение под $i$-м деревом, иначе можно. Деревья нумеруются с нуля. В следующей строке число $q$ $(1 \le q \le 2\cdot10^5)$ — количество посадок растений. Затем в следующих $q$ строках даны по три целых числа: $a_i$ $b_i$ $c_i$ $(0 \le a_i, b_i, c_i \le 10^9)$ Обратите внимание, что концы отрезков $[l_i, r_i]$ и число $k_i$ закодированы, и чтобы их получить нужно выполнить соответствующие преобразования: { \center $l_i = (a_i \oplus (t*lastans)) \mod n, \quad r_i = (b_i \oplus (t*lastans)) \mod n, \quad k_i = ((c_i \oplus (t*lastans)) \mod n) +1 $ \center
} где $lastans$ — последний ответ на запрос (изначально $lastans$ равен $0$). Если значение $l_i$ получилось больше значения $r_i$, то нужно поменять местами значения $l_i$ и $r_i$. Здесь $\oplus$ обозначает операцию побитового XOR или исключающего ИЛИ. Данная операция существует во всех современных языках программирования, например, в языках C++ и Java она обозначена как <<$\string^$>>, в Pascal — как <>. Операция $a \mod b$ означает взятие остатка от деления $a$ на $b$.
Формат выходного файла
Выведите $q$ строк. В $i$-й строке выведите одно число — ответ для $i$-го запроса.
Система оценки
Данная задача содержит пять подзадач, в каждой подзадаче выполняются ограничения из условий:
  1. $n \le 100$, $k_i = 1$, $t = 0$. Оценивается в $7$ баллов.
  2. $n \le 2000$, $q \le 2000$. Оценивается в $12$ баллов.
  3. $n \le 10^5$, $q \le 10^5$, $k_i \le 10$, $t = 0$ . Оценивается в $21$ баллов.
  4. $n \le 2\cdot10^5$, $q \le 2\cdot10^5$, $t = 0$ . Оценивается в $23$ баллов.
  5. Ограничения из условия задачи. Оценивается в $37$ баллов.
Пример:
Вход 
7 0
0 1 1 0 1 1 0
6
0 2 1
0 6 0
0 6 1
1 4 2
0 6 5
1 5 5
Ответ
1
4
2
2
1
1
( Aidos Nurmash )
комментарий/решение олимпиада
Задача №2. 

Задача C. Претенденты на ГОИ

Ограничение по времени:
1 секунда
Ограничение по памяти:
32 мегабайта

Каждые четыре года среди всех стран проводится <<Гладиаторская Олимпиада по Информатике>>. Это уникальное в своем роде соревнование, в котором участникам нужно иметь не только силу, но и высокий интеллект. В Берляндии сейчас приятная головная боль, в стране $N$ различных претендентов на Олимпиаду. Уровень каждого претендента обозначается числом, $i$-й претендент имеет уровень $i$. Берляндии как сильной в информатике стране разрешено отправлять любое количество участников на Олимпиаду, но в стране все равно планируют провести отбор. На отборочный раунд выбирается некоторое ненулевое количество претендентов, затем проводят $M$ туров. Далее в $i$-м туре проделываются следующие операции:
  1. Если количество оставшихся претендентов хотя бы $a_i$, то список претендентов покидают $a_i$ претендентов с минимальным уровнем. Далее заново повторяется $i$-й тур.
  2. Если количество оставшихся претендентов строго меньше чем $a_i$, то переходится к следующему туру. За исключением случая когда $i=M$, в этом случае отбор завершается.
Заметим тот факт, что после выбора претендентов на отборочные туры финальный список оставшихся претендентов определяется однозначно. Журналисты решили заранее описать всевозможные случаи и посчитать общее количество оставшихся претендентов по всем возможным изначальным выборкам претендентов. Так как это значение может быть большим выведите остаток по модулю $P$.
Формат входного файла
В первой строке входных данных даны три целых числа $M$, $N$ и $P$ ($1 \le M \le 1000$, $1 \le P, N \le 10^9$) — количество раундов, количество претендентов и число по которому надо взять остаток. Заметим, что $P$ необязательно простое число. В следующей строке даны $M$ целых чисел $a_i$ ($1 \le a_i \le 1000$) — число для $i$-го раунда.
Формат выходного файла
Выведите одно целое число — ответ на задачу.
Система оценки
Данная задача содержит пять подзадач, в каждой подзадаче выполняются ограничения из условий:
  1. $n \le 18$. Оценивается в $10$ баллов.
  2. $n \le 1000$. Оценивается в $18$ баллов.
  3. $n \le 10^6$, $P = 999999937$. Оценивается в $21$ баллов.
  4. Только ограничения из условия. Оценивается в $51$ баллов.
Пример:
Вход 
3 4 100000
7 3 4
Ответ
17
( Aidos Nurmash )
комментарий/решение олимпиада
Задача №3. 

Задача D. Красивая последовательность

Ограничение по времени:
1.5 секунд
Ограничение по памяти:
16 мегабайт

Подпоследовательность — это последовательность, которую можно получить из другой последовательности путем удаления некоторых элементов, не меняя порядок оставшихся элементов. Вам даны две последовательности целых неотрицательных чисел размера $n$: $a_1, a_2, \ldots, a_n$ и размера $m$: $b_1, b_2, \ldots, b_m$. Назовем последовательность из $k$ целых чисел $c_1, c_2, \ldots, c_k$ красивой, если выполняются следующие условия: Найдите максимальную длину красивой последовательности и количество различных красивых последовательностей максимальной длины по модулю $10^9 + 9$.
Формат входного файла
В первой строке входных данных дано целое положительное число $n$ ($1 \le n \le 10^4$)~— размер последовательности $a$. Вторая строка содержит $n$ целых неотрицательных чисел $a_i$ ($1 \le a_i \le 20000$)~— последовательность $a$. В третьей строке содержится целое положительное число $m$ ($1 \le m \le 10^4$)~— размер последовательности $b$.Четвертая строка содержит $m$ целых неотрицательных чисел $b_i$ ($1 \le b_i \le 20000$)~— последовательность $b$. Числа в обеих последовательностях задаются через одиночный пробел.
Формат выходного файла
Выведите два целых числа ответ на задачу. Если ответа несуществует выведите два нуля.
Система оценки
Данная задача содержит четыре подзадачи:
  1. $1 \leq n \leq 20$, $1 \le m \le 10$. Оценивается в $9$ баллов.
  2. $1 \leq n \leq 1000$, $1 \le m \le 20$. Оценивается в $9$ баллов.
  3. $1 \leq n \leq 500$, $1 \le m \le 500$. Оценивается в $28$ баллов.
  4. $1 \leq n \leq 10^4$, $1 \le m \le 10^4$. Оценивается в $54$ баллов.
Примеры:
Вход 
1
1
1
2
Ответ
0 0
Вход 
7
1 5 3 4 2 5 2
5
1 3 5 4 2
Ответ
3 6
Вход 
4
1 1 3 2
4
1 3 2 2
Ответ
3 1
( Aidos Nurmash )
комментарий/решение олимпиада
Задача №4. 

Задача A. Занимательная игра

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт

Недавно Айдос изучая культуру древних народов горных местностей, обнаружил одну очень занимательную игру. Как верили создатели этой игры, она играла очень важную роль в культуре и помогала развивать дедуктивное мышление людей всех возрастов. Айдос проникся интересностью игры и решил перевести ее на современный лад. Вот, что у него получилось. Изначально вам дается неориентированный граф с $n$ вершинами и $m$ ребрами. У каждой вершины $v$ есть значение $a_v$. Предлагается произвести над этим графом $q$ операций. Операции могут быть четырех типов:
  1. Добавить ребро между существующими вершинами
  2. Удалить существующее ребро из графа
  3. Изменить значение одной вершины
  4. Среди соседей заданной вершины найти $k$-ю по значению вершину.
Замечание. В графе могут быть кратные ребра и не гарантируется, что граф связный.
Формат входного файла
Первая строка входных данных содержит три целых чисел $n, m, q$ через пробел — количество вершин, ребер и операций $(1 <= n, m, q <= 2 \cdot 10^5)$. Вторая строка содержит $n$ целых чисел $a_1, a_2, ..., a_n$ через пробел — значения вершин $(1 <= a_i <= 10^9)$. Следующие $m$ строк содержат описания ребер графа, по два целых числа $u, v$ в каждой строке — неориентированное ребро между вершинами $u$ и $v$ $(1 <= u, v <= n)$. В каждой из следующих $q$ строк содержатся описания запросов. Каждое описание соответствует одному из следующих видов:
Формат выходного файла
На каждый запрос типа 4 выведите в новой строке номер вершины согласно требованиям в запросе.
Система оценки
Данная задача содержит шесть подзадач:
  1. $1 <= n, q <= 100$. Оценивается в 6 баллов.
  2. $1 <= n, q <= 10000$, также в этой подзадаче нет второго типа запроса. Оценивается в 7 баллов.
  3. $1 <= n, q <= 50000$. Оценивается в 22 баллов.
  4. $1 <= n, q <= 200000$, $k=1$, также в этой подзадаче нет третьего типа запроса. Оценивается в 9 баллов.
  5. $1 <= n, q <= 200000$, также в этой подзадаче нет третьего типа запроса. Оценивается в 12 баллов.
  6. Ограничения из условия. Оценивается в 43 баллов.
Пример:
Вход 
3 2 8
3 1 2
1 2
2 3
4 2 1
4 2 2
1 1 3
4 3 2
3 1 2
4 3 2
2 1 3
4 3 1
Ответ
3
1
1
1
2
( Aidos Nurmash )
комментарий/решение(1) олимпиада
Задача №5. 

Задача C. Маглы наступают

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт

Интернет в мире представляется в виде $n$ вершин и $n - 1$ ребер, каждое ребро соединяет две вершины, и возможно добраться из каждой вершину в каждую, передвигаясь по ребрам. В каждой вершине живет Волшебник. Волшебники — очень дружелюбные существа, но они могут существовать только парами. 2 Волшебника являются парой, если они находятся в соседних вершинах и решили быть парой. У Волшебника не может быть большой одной пары. Маглы решили заблокировать некоторые вершины дерева, а заодно и забрать Волшебников, живущих в них. Каждая блокировка представляет собой $k$ вершин дерева, которые будут заблокированы. Из каждой заблокированной вершины Маглы забирают Волшебника. После блокировки наступает паника и Волшебники ищут себе пару. Если хотя бы один Волшебник (среди тех, кого не забрали) не найдет себе пару, наступает Хаос. Обратите внимание, Волшебники разбиваются на пары так, чтобы образовать как можно количество пар. У Волшебников есть $q$ предположений того — какие вершины будут блокировать. И на каждый из этих предположений, Волшебникам интересно, будет ли Хаос если случится такая блокировка.
Формат входного файла
В первой строке входных данных дается два числа $n$, $q$ ($1 <= n, q <= 5*10^5$) — количество вершин и количество предположений блокировок соответственно. В следующих $n-1$ строках даются два числа $u$, $v$ ($1 <= u, v <= n$) — вершины, между которыми есть ребро. В следующих $q$ строках подаются описания блокировок в следующем виде: $k, a_1, a_2, \dots, a_k$ $(0 <= k <= n, 1 <= a_i <= n)$ — количество и номера заблокированных вершин.
Формат выходного файла
Выведите $q$ чисел, разделенных пробелами. Для каждой блокировки в порядке входных данных выведите $1$, если все Волшебники смогут разбиться на пары (Хаос не наступит), и $0$, если нет (Хаос наступит).
Система оценки
Определим $sum(k)$ как суммарное количество вершин во всех блокировках. 1. $1 <= n, q, sum(k) <= 3000$, в дереве нет вершин, у которых больше 2 соседей. Оценивается в $13$ баллов. 2. $1 <= n, q, sum(k) <= 3000$. Оценивается в $17$ баллов. 3. $1 <= n, q, sum(k) <= 100000$. Оценивается в $22$ баллов. 4. $1 <= n, q, sum(k) <= 100000$. $k_i <= 1$. Оценивается в $19$ баллов. 5. $1 <= n, q, sum(k) <= 500000$. Оценивается в $29$ баллов.
Пример:
Вход 
3 3
1 2
2 3
1 1
1 2
1 3
Ответ
1 0 1
Замечание
После блокировки первой вершины или третьей вершины, остаются лишь 2 вершины, которые связаны ребром и поэтому могут образовать пару, что и делают. В случае удаления 2ой вершины, даже если Волшебники хотят образовать пару, они не могут, так как не связаны прямым ребром. ( Aidos Nurmash )
комментарий/решение олимпиада
Задача №6. 

Задача E. Сложная сумма

Ограничение по времени:
2.5 секунд
Ограничение по памяти:
512 мегабайт

Дан массив из $n$ чисел, а также $m$ запросов. Каждый запрос содержит два числа $l$ и $r$ ($1 <= l <= r <= n$). Необходимо для каждого запроса вычислить сумму всех подмассивов $f(a[x...y])^T$ от $l$ до $r$, где $a[x...y]$ - это часть исходного массива, начинающаяся с $x$ и заканчивающаяся $y$ ($l <= x <= y <= r$), то есть массив [$a_{x}, a_{x+1}, ..., a_y$]. Для массива $b$ длины $k$, функция $f(b)$ находит массив $c$ длины $k$, который представляет собой префикс-максимумы массива $b$, а затем считает количество уникальных чисел в массиве $c$. Более формально, пусть $c_i$ = max($b_1, b_2, ..., b_i$). Тогда $f(b)$ равна количеству уникальных чисел в массиве $c$. Например, для массива $b = [3, 1, 4, 1, 5, 9, 2, 6, 5]$, мы получаем массив префикс-максимумов $c = [3, 3, 4, 4, 5, 9, 9, 9, 9]$. Затем мы считаем количество уникальных чисел в $c$, которое равно $4$ ($3, 4, 5$ и $9$). Ваша задача - написать программу, которая будет для каждого запроса будет находить сумму всех его подмассивов. Так как ответ может быть очень большим, выведите его по модулю $10^9 + 7$.
Формат входного файла
В первой строке заданы три целых числа $n$, $m$ и $T$($1 <= n,m <= 5 \cdot 10^5, 1 <= T <= 2$). Во второй строке заданы $n$ целых чисел $a_1, a_2, ..., a_n$($1 <= a_i <= n$). В следующих $m$ строках заданы по два целых числа $l_i$ и $r_i$ ($1 <= l_i <= r_i <= n$).
Формат выходного файла
Выведите $m$ целых числа — ответ на каждый запрос по модулю $10^9 + 7$.
Примеры:
Вход 
5 6 2
1 3 2 1 4
1 5
2 4
3 5
1 3
2 3
4 5
Ответ
41
6
12
12
3
6
Вход 
6 5 1
4 3 2 5 4 6
1 4
2 5
3 6
4 6
1 6
Ответ
13
14
16
8
35
Замечание
Рассмотрим $4$-й запрос первого примера: $l_4 = 1, r_4 = 3$. Получается нам нужно посчитать сумму $f(a[1...1])^2 + f(a[1...2])^2 + f(a[1...3])^2 + f(a[2...2])^2 + f(a[2...3])^2 + f(a[3...3])^2 = 1 + 2^2 + 2^2 + 1 + 1 + 1 = 12$. $f(a[1..3]) = f([a_1, a_2, a_3]) = f(1, 3, 2) = 2$, так как массив префиксных максимумов будет выглядит как $[1, 3, 3]$ и в ней два различных числа. ( Aidos Nurmash )
комментарий/решение олимпиада