Сергей работает системным администратором в очень крупной компании. Естественно, в круг его обязанностей входит резервное копирование информации, хранящейся на различных серверах и «откат» к предыдущей версии в случае возникновения проблем.
В данный момент Сергей борется с проблемой недостатка места для хранения информации для восстановления. Он решил перенести часть информации на новые сервера. К сожалению, если что-то случится во время переноса, он не сможет произвести откат, поэтому процедура переноса должна быть тщательно спланирована.
На данный момент у Сергея хранятся \(n\) точек восстановления различных серверов, пронумерованных от 1 до \(n\). Точка восстановления с номером \(i\) позволяет произвести откат для сервера \(a_i\). Сергей решил разбить перенос на этапы, при этом на каждом этапе в случае возникновения проблем будут доступны точки восстановления с номерами \(l, l + 1, \ldots, r\) для некоторых \(l\) и \(r\).
Для того, чтобы спланировать перенос данных оптимальным образом, Сергею необходимо научиться отвечать на запросы: для заданного \(l\), при каком минимальном \(r\) в процессе переноса будут доступны точки восстановления не менее чем \(k\) различных серверов.
Помогите Сергею.
Первая строка входного файла содержит два целых числа \(n\) и \(m\) (\(1 \le n, m \le 10^5\)), разделенные пробелами — количество точек восстановления и количество серверов. Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) — номера серверов, которым соответствуют точки восстановления (\(1 \le a_i \le m\)).
Третья строка входного файла содержит \(q\) — количество запросов, которые необходимо обработать (\(1 \le q \le 100\,000\)). В процессе обработки запросов необходимо поддерживать число \(p\), исходно оно равно 0. Каждый запрос задается парой чисел \(x_i\) и \(y_i\), используйте их для получения данных запроса следующим образом: \(l_i = \left((x_i + p) \bmod n\right) + 1\),
\(k_i = \left((y_i + p) \bmod m\right) + 1\) (\(1 \le l_i,x_i \le n\), \(1\le k_i, y_i \le m\)). Пусть ответ на \(i\)-й запрос равен \(r\). После выполнения этого запроса, следует присвоить \(p\) значение \(r\).
На каждый запрос выведите одно число — искомое минимальное \(r\), либо 0, если такого \(r\) не существует.
7 3 1 2 1 3 1 2 1 4 7 3 7 1 7 1 2 2
1 4 0 6
Есть квадратная клетчатая плоскость состоящая из n × n клеток (1 ≤ n ≤ 1000). Изначально в каждой клетке записано значение ноль. Ваша задача — написать программу, умеющую отвечать на следующие запросы:
В первой строке входного файла содержится два числа — n и k — размер доски и число запросов соответственно. Следующие k строк содержат сами запросы. Гарантируется, что общее число запросов не превосходит 300 000.
Для каждого запроса типа GET выведите в отдельную строку одно целое число — ответ на соответствующий запрос.
5 15 ADD 1 1 ADD 2 2 ADD 3 3 ADD 4 4 ADD 5 5 ADD 1 5 ADD 2 4 ADD 3 3 ADD 4 2 ADD 5 1 GET 1 1 5 5 GET 2 1 5 5 GET 1 2 5 5 GET 2 2 4 4 GET 3 3 3 3
10 8 8 6 2
При написании программы, проверяющей ответ участника для задачи 3204 "Отрезки на прямой возвращаются" (ссылка на задачу) (прочитайте её условие!), жюри столкнулось с трудностями, превосходящими сложность самой задачи. С мыслью "почему бы и нет" написание такой программы было решено также включить в комплект задач.
Проверяющей программе доступно три блока информации:
Ваша задача - написать программу, которая по этим данным определит, правильно ли программа абстрактного участника посчитала ответ.
Вход состоит из трёх частей. Первая часть - число \(N\) (\(1 \le N \le 100\,000\)) и следом \(N\) пар \(a_i\), \(b_i\) (\(-10^9 \le a_i \lt b_i \le 10^9\)). Далее идут \(N\) чисел, каждое из которых от 0 до \(N\), \(i\)-е равно номеру отрезка, являющегося одним из непосредственно содержащих \(i\)-й, либо нулю - по мнению абстрактного участника. Далее идут ещё \(N\) чисел в том же формате - ответ жюри на эту задачу.
Входные данные всегда корректны. Это означает, например, что ответ участника не нужно проверять на соответствие формату и что ответ жюри точно правильный.
Выведите \(N\) строк. В \(i\)-й строке должен быть вердикт для \(i\)-го отрезка. Выведите OK, если ответ абстрактного участника правильный, и WA - иначе.
Тесты состоят из четырёх групп.
4 2 3 0 4 1 6 0 5 2 2 1 0 3 4 0 0
OK WA WA OK
Вам нужно напечатать \(N\) слов на Movable Type Printer. Movable Type Printers — это старые принтеры, для работы которых требуется ставить маленькие металлические кусочки (каждый из кусочков содержит одну букву) в определенном порядке, образуя таким образом слова. Потом все они вдавливаются в лист бумаги. Таким образом печатается одно слово. Ваш принтер позволяет делать следующие операции:
Изначально на принтере содержится пустое слово. В конце печати на принтере можно оставить непустое слово. Слова, которые вам даны, вы можете печатать в произвольном порядке.
Каждая из трёх операций занимает одну единицу времени. Вам нужно найти последовательность операций, которая печатает данные \(N\) слов за минимальное время. Если минимальных последовательностaей несколько, выведите любую.
Ваша программа должна считать следующие входные данные:
Ваша программа должна вывести следующие данные:
3 print the poem
20 t h e P - - - p o e m P - - - r i n t P