Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Шахматные баталии#38386

Ильдар и Ваня устали постоянно играть в шахматы, поэтому они придумали новую шахматную игру.

Игра происходит на шахматном поле размером 2n×2m. Это поле имеет 2n строк и 2m столбцов. Для удобства будем обозначать как (i, j) клетку поля, которая находится в i-й строке и j-м столбце. Клетки этого поля покрашены в черный и белый цвета шахматной раскраской. Более точно, клетка (i, j) имеет белый цвет, если i + j чётно, и чёрный цвет в противном случае.

Игра устроена следующим образом. Ильдар вырезает некоторые белые клетки поля. После этого он предлагает Ване попробовать решить следующую задачу: может ли он на не вырезанных белых клетках поля расставить nm шахматных королей так, что никакие два выставленных короля не бьют друг друга, то есть не стоят на клетках поля, соседних по стороне или углу.

Конечно, Ильдар планирует сделать игру интересной и выставить несколько непростых для Вани комбинаций вырезанных клеток. Для этого он попросил у вас помощи. Чтобы перед игрой понять, как лучше всего действовать, он хочет потренироваться. Для этого, он берёт пустое поле и хочет q раз либо вырезать какую-то белую клетку, либо вернуть на поле какую-то ранее вырезанную клетку. После каждого изменения он бы хотел знать, каким будет ответ на задачу для Вани.

Помогите Ильдару сделать игру интересной! Напишите программу, которая будет отвечать на его запросы.

Формат входных данных
В первой строке находится три целых числа n, m, q (1 ≤ n, m, q ≤ 200 000) — количество пар строк шахматной доски, количество пар столбцов шахматной доски и количество запросов.
Следующие q строк описывают запросы Ильдара. Каждая из этих строк содержит два целых числа i, j (1 ≤ i ≤ 2n, 1 ≤ j ≤ 2m, i+j четно). Если клетка (i, j) не вырезана, то Ильдар её вырезает, иначе он возвращает её обратно на поле.

Формат выходных данных
Выведите q строк. В i-й из этих строк выведите ответ на задачу для доски, полученной после i первых запросов Ильдара.
Выведите «YES» (без кавычек), если Ваня может так расставить шахматных королей на не вырезанные белые клетки поля, что никакие два короля не будут бить друг друга. Иначе выведете «NO» (без кавычек).

Примеры

№	Входные данные	Выходные данные
1	1 3 3 1 1 1 5 2 4	YES YES NO
2	3 2 10 4 2 6 4 1 3 4 2 6 4 2 2 2 4 1 3 4 4 3 1	YES YES NO NO YES YES NO YES YES NO

Замечание
В первом примере, после второго запроса будут вырезаны клетки (1, 1) и (1, 5). Тогда Ваня может поставить три короля на клетки (2, 2), (2, 4) и (2, 6).
После третьего запроса будут вырезаны клетки (1, 1), (1, 5) и (2, 4). Тогда остаётся всего три пустые клетки (2, 2), (1, 3) и (2, 6). Ваня не может поставить трех королей на эти клетки, потому что короли в клетках (2, 2) и (1, 3) бьют друг друга, так как эти клетки соседние по углу.

Дерево отрезков, RSQ, RMQ

✓ 2✗ 31 100средняяВойти и решать

Организация коров фермера Джона 2#38136

Из N коров выбирается делегация (1≤N≤2⋅10⁵). Они стоят в ряд, корова i имеет породу b_i.

Делегация будет состоять из непрерывного участка коров не менее трёх, то есть коровы l…r для целых l и r удовлетворяющих условиям 1≤l<r≤N и r−l≥2. Три коровы в выбранном интервале помечаются как лидеры делегации. Две граничные коровы обязательно должны быть лидерами. Кроме того, каждый лидер должен иметь породу отличную от всех остальных коров в делегации (лидеры или не лидеры).

Определите количество способов которыми можно выбрать делегацию. Две делегации рассматриваются различными, если у них отличаются члены или лидеры.

Входные данные:
Первая строка содержит N.
Вторая строка содержит N целых чисел b₁,b₂,…,b_N, каждое в интервале [1,N].
Выходные данные:
Количество возможных делегаций на одной строке.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 1 2 3 4 3 2 5	9	Каждая делегация соответствует одному из следующих триплетов лидеров: (1,2,3),(1,2,4),(1,3,4),(1,4,7),(2,3,4),(4,5,6),(4,5,7),(4,6,7),(5,6,7).

Дерево отрезков, RSQ, RMQ

✓ 1✗ 1—Войти и решать

Схемы маршрутизации#38135

Рассмотрим сеть из N (2≤N≤100) вершин, помеченных 1…N. Каждая вершина обозначена как посылатель, получатель или ни то, ни другое. Количество посылателей S равно количеству получателей (S≥1).
Связи между двумя вершинами в сети могут быть описаны как список направленных ребер каждое в виде i→j, обозначающее, что вершина i может передать информацию вершине j. Интересно, что все эти рёбра удовлетворяют свойству i<j, кроме K которые удовлетворяют свойству i>j (0≤K≤2). Нет циклов (ребер вида i→i).

Описание схемы маршрутизации состоит из множества S направленных путей от посылателей к получателям таких, что никакие два из этих путей не имею общую конечную точку. То есть пути соединяют различных посылателей с различными получателями. Путь от посылателя s к получателю r может быть описан как последовательность вершин

s=v₀→v₁→v₂→?→v_e=r

такая что направленные ребра vi→vi+1 существуют для всех 0≤i<e. Одна вершина может появиться более чем один раз в одном и том же пути.
Посчитайте количество различных схем маршрутизации, таких, что каждое направленное ребро проходится ровно один раз. Поскольку ответ может быть очень большим, выводите его по модулю 10⁹+7. Гарантируется, что существует хотя бы одна схема маршрутизации, удовлетворяющая ограничениям.

Каждый ввод содержит T (1≤T≤20) тестов, которые требуется решать независимо. Гарантируется, что сумма N² всех тестов не превысит 2⋅10⁴.

Входные данные:
Первая строка содержит T, количество тестов.
Первая строка каждого теста содержит целые числа N и K. Заметим, что S не определяется явно во вводе.

Вторая строка каждого теста содержит строку длины N. i-ый символ строки равен S если i-ая вершина посылатель, R - если i-ая вершина - получатель, . - если i-ая вершина - ни то, ни другое. Количества символов R и S равны. Есть хотя бы один символ S.

Каждая из N последующих строк теста содержит битовую строку из N нулей и единиц. j-ый бит в i-ой строке равен 1, если существует направленное ребро от вершины i к вершине j, и 0 в протвном случае. Поскольку петель нет, на главной диагонали все нули. Более того имеется ровно K единиц ниже главной диагонали.

Последовательные тесты разделены пустыми строками для читабельности.

Выходные данные:
Для каждого теста выведите количество схем маршрутизации таких, что каждое ребро проходится ровно один раз, по модулю 109+7. Гарантируется, что существует хотя бы одна валидная схема маршрутизации.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 8 0 SS....RR 00100000 00100000 00011000 00000100 00000100 00000011 00000000 00000000 13 0 SSS.RRRSS.RR. 0001000000000 0001000000000 0001000000000 0000111000000 0000000000000 0000000000000 0000000000000 0000000001000 0000000001000 0000000000110 0000000000000 0000000000000 0000000000000	4 12	Для первого теста ребра таковы 1→3,2→3,3→4,3→5,4→6,5→6,6→7,6→8. Имеется четыре схемы маршрутизации: 1→3→4→6→7,2→3→5→6→8 1→3→5→6→7,2→3→4→6→8 1→3→4→6→8,2→3→5→6→7 1→3→5→6→8,2→3→4→6→7 Для второго теста 1→4,2→4,3→4,4→5,4→6,4→7,8→10,9→10,10→11,10→12. Одна из возможных схем маршрутизации: 1→4→5 2→4→7 3→4→6 8→10→12 9→10→11 В общем случае посылатели {1,2,3} могут маршрутизироваться некоторой перестановкой получателей {5,6,7}, и посылатели {8,9} могут маршрутизироваться некоторой перестановкой получателей {11,12} давая ответ 6 ⋅ 2=12.
2	2 5 1 SS.RR 00101 00100 10010 00000 00000 6 2 S....R 001000 000100 010001 000010 001000 000000	3 1	Для первого теста, ребра 1→3,1→5,2→3,3→1,3→4. имеется три схемы маршрутизации: 1→3→1→5, 2→3→4 1→3→4, 2→3→1→5 1→5, 2→3→1→3→4 Для второго теста 1→3,2→4,3→2,3→6,4→5,5→3. Имеется только одна схема мартшрутизации: 1→3→2→4→5→3→6.
3	5 3 2 RS. 010 101 100 4 2 .R.S 0100 0010 1000 0100 4 2 .SR. 0000 0011 0100 0010 5 2 .SSRR 01000 10101 01010 00000 00000 6 2 SS..RR 001010 000010 000010 000010 100101 000000	2 1 2 6 24

Динамическое программирование на графах Древовидные структуры данных

✓ 1✗ 0—Войти и решать

Организация коров фермера Джона#38133

Организация коров фермера Джона (UCFJ) направляет делегацию на Международную олимпиаду по овцеводству (IOI).
N коров участвуют в выборе делегации (1≤N≤2⋅10⁵). Они стоят в ряд, и корова i имеет породу b_i.

Делегация состоит из непрерывного интервала как минимум двух коров - то есть из коров l…r для целых l и r удовлетворяющих 1≤l<r≤N. две внешние коровы выбранного интервала называются "лидерами". Чтобы избежать конфликта между породами коров каждый лидер должен иметь породу отличающуюся от остальных коров делегации (лидеров и не лидеров).

Определите количество способов выбрать делегацию.

Входные данные:
Первая строка содержит N.
Вторая строка содержит N целых чисел b₁,b₂,…,b_N, каждое в интервале [1,N].

Выходные данные:
Количество возможных делегаций, на отдельной строке.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 1 2 3 4 3 2 5	13	Каждая делегация соответствует одной из следующих пар лидеров: (1,2),(1,3),(1,4),(1,7),(2,3),(2,4),(3,4),(4,5),(4,6),(4,7),(5,6),(5,7),(6,7).

Двоичное дерево поиска

✓ 4✗ 111 000средняяВойти и решать

Порталы#38132

Беси расположена на сети из N (2≤N≤10⁵) вершин помеченных 1…N и 2N порталов помеченных 1…2N. Каждый портал соединяет две различных вершины u и v (u≠v). Множество порталов может соединять некоторую пару вершин.
Каждая вершина v соседняя для четырёх различных порталов. Список порталов вершины v задаётся как pv=[p_v,1,p_v,2,p_v,3,p_v,4].

Ваше текущее положение может быть представлено упорядоченной парой (current vertex,current portal); то есть парой (v,p_v,i) где 1≤v≤N и 1≤i≤4. Вы можете использовать одну из следующих операций для изменения своего текущего положения:

Изменить текущую вершину перемещением через текущий портал.
Переключить текущий портал. В каждой вершине первые два портала в списке объединены в пару и последние два портала в списке также объединены в пару. Поэтому если Ваше текущее состояние (v,p_v,2), то Вы можете переключиться чтобы использовать портал (v,p_v,1) и обратно. Аналогично, если Ваше текущее положение (v,p_v,3) Вы можете переключиться на портал (v,p_v,4) и обратно. никакие другие переключения не разрешены (например, Вы не можете переключиться с портала pv,2 на портал) p_v,4).
Всего имеется 4N различных состояний. К несчастью, может не оказаться, что что любое состояние достижимо из любого с помощью последовательности заданных операций. Поэтому, за цену cv (1≤c_v≤1000) мунов вы можете сделать перестановку списка порталов соседних вершине v, в любом желаемом Вами порядке. После этого первые два портала в списке объединяются в одну пару, а последние два портала - в другую пару.

Например, если Вы переставить порталы вершины v в порядке [p_v,3,p_v,1,p_v,2,p_v,4], Это означает. что если Вы в вершине v,

Если Вы в портале p_v,1, Вы можете переключиться на портал p_v,3 и обратно
Если Вы в портале p_v,2, Вы можете переключиться на портал p_v,4 и обратно
Теперь Вы не можете переключаться с портала p_v,1 на p_v,2, или с портала p_v,3 на портал p_v,4 и обратно.
Вычислите минимальное количество мунов, требуемых для модификации сети таким образом, чтобы сделать достижимым каждое состояние из каждого состояния. Гарантируется, что тестовые данные сконструированы таким образом, что существует хотя бы один способ такой модификации сети.

Входные данные:
Первая строка содержит N.
Каждая из следующих N строк описывает вершину. Строка v+1 содержит 5 разделённых одиночными пробелами целых чисел c_v,p_v,1,p_v,2,p_v,3,p_v,4.
Гарантируется, что для каждой v все p_v,1,p_v,2,p_v,3,p_v,4 различны, и каждый портал появляется в списках ровно двух вершин.

Выходные данные:
Одна строка содержит минимальное количество мунов требуемых для модификации сети чтобы сделать возможным достижимость каждого состояния из другого состояния.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 10 1 4 8 9 11 1 2 5 6 12 9 10 2 3 3 4 3 6 7 15 10 8 7 5	13	Достаточно сделать перестановку списков вершин 1 и 4. Это требует c1+c4=13 мунов. Перестановки такие: p1=[1,9,4,8] и p4=[7,4,6,3].

Древовидные структуры данных Минимальный каркас Система непересекающихся множеств

✓ 2✗ 391 200средняяВойти и решать

33701#33701

Реализуйте эффективную структуру данных, позволяющую изменять элементы массивы и вычислять НОД нескольких подряд идущих элементов.

Входные данные
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.
Во второй строке вводятся N чисел от 0 до 100000 — элементы массива.
В третьей строке вводится одно натуральное число M (1 ≤ M ≤ 30000) — количество запросов.
Каждая из следующих M строк представляет собой описание запроса. Сначала вводится одна буква, кодирующая вид запроса (s — вычислить НОД, u — обновить значение элемента).
Следом за s вводятся два числа — номера левой и правой границы отрезка.
Следом за u вводятся два числа — номер элемента и его новое значение.

Выходные данные
Для каждого запроса s выведите результат. Все числа выводите в одну строку через пробел.

Ввод	Вывод
5 2 8 4 16 12 5 s 1 5 s 4 5 u 3 32 s 2 5 s 3 3	2 4 4 32

Дерево отрезков, RSQ, RMQ

✓ 4✗ 4—Войти и решать

Суммы на подотрезках#33700

Реализуйте структуру данных для эффективного вычисления сумм подряд идущих элементов массива.

Входные данные
В первой строке вводится одно натуральное число N (1 ≤ N ≤ 100000) — количество чисел в массиве.

Во второй строке вводятся N чисел от 1 до 100000 — элементы массива.

В третьей строке вводится одно натуральное число K (1 ≤ K ≤ 30000) — количество запросов на вычисление суммы.

В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).

Выходные данные
Для каждого запроса выведите сумму чисел соответствующего участка массива. Числа выводите в одну строку через пробел.

Ввод	Вывод
5 4 4 8 7 8 2 1 2 1 3	8 16

Дерево отрезков, RSQ, RMQ

✓ 56✗ 202700средняяВойти и решать

Максимумы на подотрезках#33699

Реализуйте структуру данных для эффективного вычисления максимумов подряд идущих элементов массива.

Входные данные
В первой строке вводится одно натуральное число N (\(1 <= N <= 100000\)) — количество чисел в массиве. Во второй строке вводятся N чисел от 1 до 100000 — элементы массива. В третьей строке вводится одно натуральное число K (\(1 <= K <= 30000\)) — количество запросов на вычисление максимума. В следующих K строках вводится по два числа — номера левого и правого элементов отрезка массива (считается, что элементы массива нумеруются с единицы).

Выходные данные
Для каждого запроса выведите значение максимального элемента на указанном отрезке массива. Числа выводите в одну строку через пробел.

Примеры

№	Входные данные	Выходные данные
1	5 2 2 2 1 5 2 2 3 2 5	2 5

sqrt декомпозиция Дерево отрезков, RSQ, RMQ

✓ 20✗ 122700средняяВойти и решать

Abracadabra#33316

Строка s называется супрефиксом для строки t, если t начинается с s и заканчивается на s. Например, «abra» является супрефиксом для строки «abracadabra». В частности, сама строка t является своим супрефиксом. Супрефиксы играют важную роль в различных алгоритмах на строках.

В этой задаче требуется решить обратную задачу о поиске супрефикса, которая заключается в следующем. Задан словарь, содержащий n слов t₁, t₂, …, t_n и набор из m строк-образцов s₁, s₂, …, s_m. Необходимо для каждой строки-образца из заданного набора найти количество слов в словаре, для которых эта строка-образец является супрефиксом.

Требуется написать программу, которая по заданному числу n, n словам словаря t₁, t₂, …, t_n, заданному числу m и m строкам-образцам s₁, s₂, …, s_m вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец является супрефиксом.

Входные данные

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 200 000).

Последующие n строк содержат слова t₁, t₂, …, t_n, по одному слову в каждой строке. Каждое слово состоит из строчных букв латинского алфавита. Длина каждого слова не превышает 50. Суммарная длина всех слов не превышает 10⁶. Словарь не содержит пустых слов.

Затем следует строка, содержащая целое число m (1 ≤ m ≤ 200 000).

Последующие m строк содержат строки-образцы s₁, s₂, …, s_m, по одной на каждой строке. Каждая строка-образец состоит из строчных букв латинского алфавита: Длина каждой строки-образца не превышает 50. Суммарная длина всех строк-образцов не превышает 10⁶. Никакая строка-образец не является пустой строкой.

Выходные данные

Выходной файл должен содержать m чисел, по одному на строке.

Для каждой строки-образца в порядке, в котором они заданы во входном файле, следует вывести количество слов словаря, для которых она является супрефиксом.

Ввод	Вывод
4 abacaba abracadabra aa abra 3 a abra abac	4 2 0

Бор

✓ 3✗ 41 000средняяВойти и решать

Type Printer#33314

Вам нужно напечатать N слов на Movable Type Printer. Movable Type Printers — это старые принтеры, для работы которых требуется ставить маленькие металлические кусочки (каждый из кусочков содержит одну букву) в определенном порядке, образуя таким образом слова. Потом все они вдавливаются в лист бумаги. Таким образом печатается одно слово. Ваш принтер позволяет делать следующие операции:

Добавить букву в конец слова, находящегося сейчас на принтере.
Удалить последнюю букву из слова, находящегося сейчас на принтере. Эту операцию можно делать, только если слово содержит хотя бы одну букву.
Напечатать слово, находящееся на принтере.

Изначально на принтере содержится пустое слово. В конце печати на принтере можно оставить непустое слово. Слова, которые вам даны, вы можете печатать в произвольном порядке.

Каждая из трёх операций занимает одну единицу времени. Вам нужно найти последовательность операций, которая печатает данные N слов за минимальное время. Если минимальных последовательностaей несколько, выведите любую.

Входные данные

Ваша программа должна считать следующие входные данные:

На первой строке число N (1<=N<=25000).

На следующих N строках слова, состоящие из маленьких букв латинского алфавита. Длина каждого слова не превышает 20. Все слова различны.

Выходные данные

Ваша программа должна вывести следующие данные:

На первой строке M — число операций.

На следующих M строках по одному символу — описание операций. Каждая операция описывается одним символом:

Добавление символа обозначается собственно символом.

Удаление символа обозначается символом «-» (минус, ASCII-код 45).

Операция «напечатать текущее слово» обозначается символом «P» (заглавная латинская буква P).

Ввод	Вывод
3 print the poem	20 t h e P - - - p o e m P - - - r i n t P

Бор Обход в глубину

✓ 1✗ 741 200средняяВойти и решать

Цепочка слов#33313

Цепочкой слов длины n назовем последовательность слов w₁, w₂, ..., w_n такую, что для 1 ≤ i ≤ n слово wi является собственным префиксом слова w_i + 1.

Напомним, что слово u длины k называется собственным префиксом слова v длины l, если l > k и первые k букв слова v совпадают со словом u.

Задано множество слов S = {s₁, s₂, ..., s_m}. Найдите максимальную длину цепочки слов, которую можно построить, используя (возможно, не все) слова этого множества.

Входные данные

Первая строка входного файла содержит целое число m(1 ≤ m ≤ 255). Каждая из последующих m строк содержит по одному слову из множества S.

Все слова не пусты, имеют длину, не превосходящую 255 символов, и состоят только из строчных букв латинского алфавита.

Выходные данные

В выходной файл выведите ответ на задачу.

Ввод	Вывод
3 a ab abc	3
5 a ab bc bcd add	2

Бор Обход в глубину

✓ 16✗ 46700средняяВойти и решать

Кот Гусь и случайная матрица#33256

Кот Гусь подготовил для Ника Фьюри прямоугольную таблицу a размера \(n \cdot m\), содержащую числа от 0 до p−1. Ник Фьюри сразу понял, что каждое число в этой таблице выбрано случайно равновероятно от 0 до p−1, независимо от остальных.

Ваша задача — найти прямоугольную подматрицу этой таблицы, в которой сумма делится на p. Среди всех таких подматриц нужно найти ту, в которой сумма элементов максимальна.

Формально, вам необходимо найти такие \(1 <= i_1 <= i_2 <= n\), \(1 <= j_1 <= j_2 <= m\), что сумма a_x,y по всем \(i_1 <= x <= i_2\), \(j_1 <= y <= j_2\) делится на p, и среди таких имеет максимальную сумму.

Входные данные

В первой строке расположено три целых числа n, m, p (\(1 <= n·m, p <= 1 000 000\)) — размерности матрицы и число, на которое должна делится сумма подматрицы.

В следующих n строках расположено по m целых чисел, j-е число в i-й строке равно a_i,j (\(0 <= a_{i,j} <= p ? 1\)).

Гарантируется, что каждое число в a выбрано независимо случайно равновероятно от 0 до p−1.

Выходные данные

Выведите одно целое число — максимальную сумму прямоугольной подматрицы, в которой сумма делится на p. Если таких нет, выведите 0.

Примеры

№	Входные данные	Выходные данные
1	6 7 5 0 0 3 0 1 0 4 0 2 3 0 2 2 1 2 4 1 4 4 0 3 1 1 0 2 0 3 2 3 0 3 1 0 1 2 1 2 0 0 3 3 1	65

Куча Префиксные суммы(минимумы, ...)

✓ 8✗ 1791 200средняяВойти и решать

Поддержка максимума#30755

Дана последовательность чисел. Для каждого числа вывести текущий максимум на момент его ввода.

Входные данные

Задано сначала число N (количество чисел в последовательности, 1<=N<=100000), а затем N чисел.

Выходные данные

Выведите текущие максимумы.

Примеры

№	Входные данные	Выходные данные
1	7 4 2 5 -1 4 6 2	4 4 5 5 5 6 6

Куча

✓ 128✗ 66200лёгкаяВойти и решать

Поиск минимума с помощью приоритетной очереди#30754

Дана последовательность чисел. Найти в ней наименьшее число.

Входные данные

Задано сначала число N (количество чисел в последовательности, 1<=N<=100000), а затем

N чисел.

Выходные данные

Выведите наименьшее число.

Ввод	Вывод
7 4 2 5 -1 4 6 2	-1

Куча Структуры данных

✓ 144✗ 83400лёгкаяВойти и решать

Пирамида (максимум)#30723

Напишите программу, которая будет обрабатывать последовательность запросов таких видов:

CLEAR — сделать пирамиду пустой (если в пирамиде уже были какие-то элементы, удалить все). Действие происходит только с данными в памяти, на экран ничего не выводится.

ADD n — добавить в пирамиду число n. Действие происходит только с данными в памяти, на экран ничего не выводится.

EXTRACT — вынуть из пирамиды максимальное значение. Следует и изменить данные в памяти, и вывести на экран или найденное максимальное значение, или, если пирамида была пустой, слово "CANNOT" (большими буквами).

Входные данные

Во входных данных записано произвольную последовательность запросов CLEAR, ADD и EXTRACT — каждый в отдельной строке, согласно вышеописанному формату. Данные заканчиваются строкой "END!"

Суммарное количество всех запросов не превышает 200000.

Выходные данные

Для каждого запроса типа EXTRACT выведите на стандартный выход (экран) его результат (в отдельной строке).

Ввод	Вывод
ADD 192168812 ADD 125 ADD 321 EXTRACT EXTRACT CLEAR ADD 7 ADD 555 EXTRACT EXTRACT EXTRACT END!	192168812 321 555 7 CANNOT

Куча

✓ 98✗ 170500лёгкаяВойти и решать

Cart Sorting#29658

У Акакия есть колода, состоящая из n карт. На каждой карте написано ровно одно целое число от 1 до 100 000. Возможно, что на некоторых картах написаны одинаковые числа.

Акакий решил отсортировать все карты в колоде. Для этого он по очереди берёт одну верхнюю карту из колоды и если число, написанное на ней, равно минимальному среди всех оставшихся чисел в колоде, он откладывает эту карту в сторону. В противном случае, Акакий кладёт эту карту вниз колоды и берёт сверху колоды следующую карту. Процесс заканчивается, когда в колоде не останется карт. Можно считать, что Акакий в любой момент времени знает минимальное число, записанное на какой-то из оставшихся в колоде картах, но не знает, где эта карта (или карты) находится в колоде.

Перед вами стоит задача определить суммарное количество раз, которое Акакий посмотрит верхнюю карту из колоды.

Входные данные

В первой строке следует целое положительное число n (1 ≤ n ≤ 100 000) — количество карт в колоде.

Во второй строке следует последовательность из n целых положительных чисел a₁, a₂, ..., a_n (1 ≤ a_i ≤ 100 000), где a_i равно числу, написанному на i-й сверху карте из колоды.

Выходные данные

Выведите суммарное количество раз, которое Акакий посмотрит верхнюю карту из колоды.

Ввод	Вывод
4 6 3 1 2	7
1 1000	1
7 3 3 3 3 3 3 3	7

Примечание

В первом примере Акакий посмотрит сначала карту с числом 6, положит ее вниз колоды, затем карту с числом 3, также положит ее вниз колоды, и затем карту с числом 1. Он отложит карту с числом 1, так как на ней написан минимальное число из оставшихся в колоде. После этого карты в колоде будут лежать в порядке [2, 6, 3] сверху вниз. После этого Акакий посмотрит верхнюю карту с числом 2 и отложит её. После этого карты в колоде будут лежать в порядке [6, 3] сверху вниз. Затем Акакий посмотрит карту с числом 6, положит ее вниз колоды, а затем карту с числом 3, которую отложит. После этого в колоде останется одна карта с числом 6, которую Акакий посмотрит и отложит. Таким образом, Акакий посмотрит 7 карт.

(с) Курбатов Е., 2018

Декартово дерево

✓ 1✗ 31 100средняяВойти и решать

27309#27309

Вы должны реализовать алгоритм или структуру данных, эффективно реализующих следующие запросы:

1)Добавление в массив элемента

2)Извлечение k-того по величине элемента массива (первым по величине будет считаться наименьший элемент)

Гарантируется, что каждый элемент встречается в массиве всего один раз

Входные данные:

В первой строке указано натуральное число n, за ним следует n целых чисел.

Далее вводится натуральное m - количеств запросов.

В каждой из следующих m строк содержится слово "add" или "get" и целое число k.

Все численные значения по модулю не превосходят 1000.

В первом случае вы должны дополнить массив элементом со значением k. Иначе - вывести k-тый элемент отсортированного текущего массива (индексация с единицы).

Выходные даннные:

Вы должны ответить на запрос извлечения k-того элемента массива, а именно вывести его значение на экран.

Двоичное дерево поиска Порядковые статистики

✓ 0✗ 41 300средняяВойти и решать

Trapped in the Haybales#27295

Фермер Джон получили груз из N больших стогов сена (1≤N≤100,000), и разметил их в различных положениях вдоль дороги, ведущей к амбару. К несчастью, он полностью забыл, что корова Беси пасётся вдоль дороги и может попасть в ловушку между стогами сена.

Каждый стог j имеет размер S_j и позицию Pj определяющую его положение вдоль дороги. Беси может двигаться вдоль дороги вплоть до позиции стога, но не может пересечь эту позицию. Исключение – если она прошла в этом направлении D единиц расстояния, тогда она набрала достаточно скорости, чтобы протаранить стог любого размера строго меньше чем D. Конечно после этого она может продолжить движение и таранить другие стога.

Беси может выйти на свободу если она в конце концов протаранит протаранит самый левый или самый правый стог. Вычислите общий размер участка дороги, состоящий из возможных точек старта Беси, из которых она не сможет выбраться.

ФОРМАТ ВООДА:

Первая строка ввода содержит N. Каждая из последующих N строк описывает стог, и содержит два целых числа определяющих размер и позицию в диапазоне 1…10⁹. Все позиции различны.

ФОРМАТ ВЫВОДА:

Выведите одно целое число – размер области дороги, откуда Беси не сможет выбраться.

Ввод	Вывод
5 8 1 1 4 8 8 7 15 4 20	14

Дерево отрезков, RSQ, RMQ Динамическое программирование Динамическое программирование: один параметр Структуры данных

1 200средняяВойти и решать

Switch Grass#27216

Фермер Джон обнаружил, что разные типы коров любят разные типы травы. Однако он должен правильно их высаживать, чтобы не навредить.

Ферма Джона состоит из NN (1≤N≤200,000), полей, и MM пар полей соединены двунаправленными дорожками (1≤M≤200,000). Используя эти дорожки, можно пройти от любого поля к любому другому полю. Каждая дорожка имеет целочисленную длину в интервале 1…1,000,000. Любая пара полей соединена не более чем одной прямой дорожкой.

В каждом поле ФД изначально посадил один из KK типов травы (1≤K≤N). Через некоторое время, однако, он может решить изменить тип травы на некоторых из полей. Он называет это операцией "обновления".

После каждого обновления, ФД хочет знать длину кратчайшего пути между двумя полями, имеющими различные типы травы. То есть, среди всех пар полей, имеющих различные типы травы, он хочет узнать, какие два поля ближайшие друг к другу. Гарантируется, что всегда имеется как минимум одна пара полей с различными типами травы.

В 30 процентах тестов каждое поле непосредственно соединено не более чем с 10 дорожками.

ФОРМАТ ВВОДА:

Первая строка ввода содержит четыре целых числа N, M, K, Q, где Q - количество операций обновления (1≤Q≤200,000). Следующие M строк описывают дорожки. Каждая строка содержит три целых числа A, B, L, указывающих, что есть дорожка между полями A, B и её длина L. (A, B - целые числа в интервале 1…N). Следующая строка указывает начальный тип травы для каждого поля (N целых чисел в интервале 1…K). Затем идут Q строк, каждая из которых описывает одну операцию обновления двумя целыми числами A и B, означающими, что на поле A типе травы изменён на B.

ФОРМАТ ВЫВОДА:

Для каждой операции обновления выведите длину кратчайшего пути между двумя полями с различными типами травы, после применения этой операции обновления.

Ввод	Вывод
3 2 3 4 1 2 3 2 3 1 1 1 2 3 3 2 3 1 2 2 2	1 3 3 1

Алгоритмы на графах Дерево отрезков, RSQ, RMQ Минимальный каркас Обход в глубину Структуры данных

✓ 1✗ 41 200средняяВойти и решать

Рассадка зверей#24764

Сегодня Колобок созвал всех волков и лис к себе в гости на чаепитие. Чаепитие пройдет за круглым столом, за которым всего n мест. Колобок хочет рассадить зверей по-особенному — так, чтобы волки не сидели только с волками, а лисы только с лисами. Поэтому для каждого места он записал одно целое число — сколько лис должно сидеть на расстоянии не более d от этого места, включая это место.

Два места находятся на расстоянии не более d, если между ними встречаются не более d−1 места при движении по или против часовой стрелки от одного к другому. Таким образом, для заданного места всего существует 2d + 1 место, находящееся на расстоянии не более d от него.

Теперь он хочет придумать какую-нибудь рассадку зверей, удовлетворяющую этим ограничениям.

Входные данные
В первой строке находятся два натуральных числа n, d (3 ≤ n ≤ 10⁵ , 3 ≤ 2d+1 ≤ n) — количество мест за круглым столом и расстояние d. В следующей строке находятся n неотрицательных целых чисел ai (0 ≤ a_i ≤ 2d+1) — количество лис на расстоянии не более d от этого места, включая это место. Информация о местах перечислена в порядке их следования по кругу.

Выходные данные
Если решения не существует, выведите «NO», иначе в первой строке выведите «YES», а в следу- ющей n чисел: 1 в том случае, если на этом месте сидит лиса, и 0, если на этом месте сидит волк. Если ответов несколько, разрешается вывести любой.

Ввод	Вывод
5 1 2 2 1 2 2	YES 1 0 1 0 1
9 2 3 4 4 3 3 2 2 2 2	YES 1 0 1 1 1 0 0 0 1
6 1 3 3 3 3 3 1	NO

Дерево отрезков, RSQ, RMQ НОД и алгоритм Евклида

1 300средняяВойти и решать