Каждый день к Грегори Хаусу приходит много больных, и у каждого измеряется уровень гемоглобина в крови. Данные по всем пациентам заносятся в базу данных.
Но волчанка попадается один раз на миллион, а работать с остальными неинтересно. Чтобы Хаус не выгонял больных, Кадди иногда запрашивает статистику по k последним больным: ей хочется знать сумму их уровня гемоглобина.
Также Хаус — мизантроп: он смотрит уровень гемоглобина больного, который поступил к нему позже всех, и, видя, что это точно не волчанка, выписывает его из больницы и удаляет информацию о нем из базы.
Автоматизацию процесса Хаус поручил Чейзу. Но Чейз почему-то не справился с этой задачей и попросил вас ему помочь.
Первой строкой входного файла задано число n ( 1 ≤ n ≤ 100000 ) — число обращений к базе данных. Запросы к базе выглядят следующим образом: + x ( 1 ≤ x ≤ 10 9 ) — добавить пациента с уровнем гемоглобина x в базу, - — удалить последнего пациента из базы, ? k ( 1 ≤ k ≤ 100000 ) — вывести суммарный гемоглобин последних k пациентов. Гарантируется, что k не превосходит число элементов в базе. Также гарантируется, что запросов на удаление к пустой базе не поступает. Перед началом работы база данных пуста.
Для каждого запроса " - " вывести уровень гемоглобина в крови пациента, а для каждого запроса " ? k " — суммарный гемоглобин у последних k поступивших пациентов. Ответы выводите в порядке поступления запросов.
7 +1 +2 +3 ?2 - - ?1
5 3 2 1
Вера очень много работала в этом году, подавая своим коллегам пример настоящего труженика. На восьмое марта за прекрасное исполнение служебных обязанностей Вера получила подарок — долгожданный отпуск в Теплой Стране! Тяжелые трудовые будни закончились, и Вера уже нежится на пляже на берегу Теплого Моря.
Любимое хобби Веры — пляжный волейбол, и как же Вера ждала момента, когда она сможет испытать невероятный азарт этой игры! Вера уже познакомилась с несколькими симпатичными волейболистами, но она пока не решила, какая же команда достойна иметь в своем составе такого замечательного игрока.
Каждый из N капитанов команд мечтает заполучить Веру в состав своей команды, поэтому они хотят максимально проявить себя. Так как поиграть хотят все, они решили действовать следующим образом: все N команд выстроились в очередь. Первый матч играется между двумя командами, которые стоят в очереди раньше остальных. Победитель игры остается на площадке, а проигравший отправляется в конец очереди. В каждом из следующих матчей победитель предыдущего играет с первой командой из очереди, а про- игравший в очередной встрече опять становится в конец очереди. Каждая команда имеет некоторую силу, причем для простоты будем предполагать, что силы всех команд различны, а победителем в матче является команда, сила которой больше. Матчей может быть как угодно много.
Вера решила для себя, что она будет действовать по самому справедливому принципу «считалочки»: она будет играть с одной из двух команд, играющих матч с соответствующем считалке номером \(K\). Но затем Вера поняла, что уже выбрала себе команду, в которой хотела бы играть, причем ориентируясь не только на ее силу. Ей известны \(Q\) считалок, соответствующих различным значениям \(K\). Для каждого из этих чисел \(K_i\) необходимо узнать, а кто же именно будет сражаться за столь ценный приз, то есть какие две команды будут играть в матче с номером \(K_i\).
Первая строка входных данных содержит единственное целое число \(N\) — количество команд (2 ≤ \(N\) ≤ 100 000). Вторая строка содержит \(N\) различных чисел от 1 до \(N\) — силы команд: первое число — сила команды, стоящей в начале очереди, второе — сила следующей по очереди команды, ..., последнее — сила команды, стоящей в конце очереди.
Третья строка содержит единственное целое число \(Q\) (1 ≤ \(Q\) ≤ 100 000) — количество известных Вере считалок. Каждая из следующих Q строк содержит число \(K_i\) (1 ≤ Ki ≤ 1018) — номер очередного интересующего Веру матча. Обратите внимание, \(K_i\) может быть больше \(N\).
Выведите \(Q\) строк: для каждого интересующего Веру числа \(K_i\) два числа в любом порядке — силы команд, сыграющих на \(K_i\)-м шаге. Первая строка должна содержать ответ на первый запрос, вторая — на второй и так далее.
Разберем первый тест из условия:
Таким образом, в единственном интересующем Веру третьем матче сыграют команды с силами 4 и 3.
Тесты к этой задаче состоят из четырех групп.
0. Тесты 1–2. Тесты из условия, оцениваются в ноль баллов.
1. Тесты 3–18. В тестах этой группы \(N\) ≤ 2 000, Q = 1, \(K_i\) ≤ 2 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
2. Тесты 19–25. В тестах этой группы \(N\) ≤ 100 000, 1 ≤ \(Q\) ≤ 10, \(K_i\) ≤ 100 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой группы.
3. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура, причем только в случае прохождения всех тестов из первой и второй групп. Тесты в этой группе оцениваются независимо.
4 1 3 2 4 1 3
3 4
4 2 1 4 3 3 1 5 2
2 1 4 2 2 4
Фирма NNN решила транслировать свой рекламный ролик в супермаркете XXX. Однако денег, запланированных на рекламную кампанию, хватило лишь на две трансляции ролика в течение одного рабочего дня. И при этом обязательно транслировать ровно два рекламных ролика в день.
Фирма собрала информацию о количестве покупателей в каждый момент некоторого дня. Менеджер по рекламе предположил, что и на следующий день покупатели будут приходить и уходить ровно в те же моменты времени.
Помогите ему определить моменты времени, когда нужно включить трансляцию рекламных роликов, чтобы как можно большее количество покупателей прослушало ролик.
Ролик длится ровно одну единицу времени. Для каждого момента времени известно количество покупателей, находящихся в магазине в этот момент. Между концом первой рекламы и началом следующей должна пройти как минимум К - 1 единица времени.
Первая строка содержит два числа N (моментов времени) и K (время совершения покупки одним покупателем). Гарантируется, что N > K. ( N, K ≤ 200 000 ). Во второй строке содержится N чисел a i — количество покупателей в момент времени i . ( 0 ≤ a i ≤ 2 000 000 000 ).
Выведите единственное число — количество просмотревших рекламу покупателей.
5 2 3 5 1 4 2
9
Служба безопасности Земли хочет уничтожить корабль враждебно настроенных инопланетян. Служба безопасности уже повредила корабль и заставила его сесть в пустыне. Корабль построен из кубических отсеков единичного размера и нижний слой имеет форму прямоугольника размером N × M . На рисунке показан пример вида сверху на корабль размером N = 4 , M = 8 .
Отсеки корабля сделаны из сверхпрочного металла, поэтому для разрушения корабля используются лазеры. Лазерные установки были развернуты напротив четырех боковых сторон корабля, и они периодически выпускают лучи, перпендикулярные сторонам корабля, в сторону различных отсеков корабля. Каждый луч разрушает R первых отсеков, встретившихся на его пути. Если над уничтоженным отсеком находятся другие отсеки, то они сдвигаются вниз. Так же лазеры могут стрелять только по нижним бокам.
После K выстрелов было решено нанести по кораблю авиаудар. Для удара имеет смысл выбрать такой участок размером P × P , который целиком содержит максимальное количество уцелевших отсеков, чтобы уничтожить их все.
Напишите программу, которая вычислит, какое количество целых блоков сможет уничтожить авиаудар, нанесенный на участке размером P × P .
В первой строке входного файла даны 5 целых чисел: N , M ( 1 ≤ N · M ≤ 1 000 000 ), R ( 0 < R ≤ 10 ), K ( 0 < K ≤ 300 000 ) и P ( 0 < P ≤ min ( N , M , 10) ). В каждой из следующих N строк записаны по M чисел. Число в i -ой строке и j -ом столбце описывает количество единичных блоков в соответствующей части корабля аналогично рисунку. Каждое число находится в диапазоне 1..10 6 .
В следующих K строках описаны выстрелы из лазеров. Каждая из этих строк содержит один символ и через пробел от него число. Символы определяют сторону воздействия: "W" — запад, "E" — восток, "S" — юг, "N" — север. Число определяет номер строки в случае запада и востока или столбца в случае севера и юга. Строки и столбцы соответствуют нумерации из входных данных, слои нумеруются с единицы. Каждое число находится в диапазоне 1..10 6 .
Выведите максимальное количество уцелевших отсеков после K выстрелов лазерами на участке размером P × P .
4 8 2 6 2 1 1 1 1 1 1 1 1 1 2 3 1 1 1 3 1 1 2 1 1 3 1 1 1 1 1 1 1 1 1 1 2 N 2 W 2 W 2 E 2 S 4 S 7
6
Лайнландия представляет из себя одномерный мир, являющийся прямой, на котором распологаются N городов, последовательно пронумерованных от 0 до N - 1 . Направление в сторону от первого города к нулевому названо западным, а в обратную "— восточным.
Когда в Лайнландии неожиданно начался кризис, все были жители мира стали испытывать глубокое смятение. По всей Лайнландии стали ходить слухи, что на востоке живётся лучше, чем на западе.
Так и началось Великое Лайнландское переселение. Обитатели мира целыми городами отправились на восток, покинув родные улицы, и двигались до тех пор, пока не приходили в город, в котором средняя цена проживания была меньше, чем в родном.
В первой строке дано одно число N ( 2 ≤ N ≤ 10 5 ) "— количество городов в Лайнландии. Во второй строке дано N чисел a i ( 0 ≤ a i ≤ 10 9 ) "— средняя цена проживания в городах с нулевого по ( N - 1) -ый соответственно.
Для каждого города в порядке с нулевого по ( N - 1) -ый выведите номер города, в который переселятся его изначальные жители. Если жители города не остановятся в каком-либо другом городе, отправившись в Восточное Бесконечное Ничто, выведите - 1 .
10 1 2 3 2 1 4 2 5 3 1
-1 4 3 4 -1 6 9 8 9 -1