#112541

Темы: [Дерево отрезков, RSQ, RMQ]

В одном большом городе очень много достопримечательностей и в него регулярно приезжают толпы туристов. Но просто приезжать в город неинтересно, и туристы любят осматривать достопримечательности. Все туристы — занятые люди и осматривать две достопримечательности одного и того же типа не собираются. Например, никто не пойдёт в два музея, ведь, чтобы сказать, что ты был в музее, достаточно сходить только в один. Все n достопримечательностей расположены вдоль главной улицы города. Каждая достопримечательность имеет свой тип — музей, театр, памятник... Каждый приезжающий турист заказывает в турагенстве экскурсию. Экскурсия представляет из себя проезд по каким-то достопримечательностям, стоящим подряд. Так как туристы живут в разных частях города, то не всем им удобно добираться до главной улицы. Поэтому, для i -го туриста есть границы [ l _i ; r _i ] — отрезок, в который должны попасть начало и конец экскурсии, ведь ему надо не только приехать на неё, ну и уехать потом домой. Каждый турист хочет осмотреть как можно больше достопримечательностей, но при этом он не будет смотреть более одной достопримечательности одного типа. Помогите турагенству подобрать каждому туристу подходящую ему экскурсию.

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

В первой строке входного файла задано число n (1 ≤ n ≤ 100000) — количество достопримечательностей в городе. Во второй строке заданы n целых чисел t _i (1 ≤ t _i ≤ 10 ⁹ ) — типы достопримечательностей. В третьей строке задано число m (1 ≤ m ≤ 100128) — количество туристов. Далее, в m строках заданы описания туристов в формате l _i r _i (1 ≤ l _i ≤ r _i ≤ n ) , где l _i , r _i — отрезок, в который должны попасть начало и конец экскурсии для i -го туриста.

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

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

Примеры

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

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

#112544

Игра на бирже

Темы: [Дерево отрезков, RSQ, RMQ]

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

Идея анализа состоит в следующем: по заданным котировкам акции в течение n последовательных дней, требуется выбрать подпоследовательность котировок, которая удовлетворяет следующему свойству: любые две соседние котировки в выбранной подпоследовательности должны отличаться не менее чем на k . Например, если котировки равны, соответственно, 1014, 1024, 1034, 1045, 1030, 998 и k = 15 , то подпоследовательность котировок 1014, 1034, 998 является допустимой. Выбранная подпоследовательность должны быть как можно длиннее. Так, в приведенном примере выбранная последовательность не является оптимальной, подпоследовательность 1014, 1045, 1030, 998 лучше.

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

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

Первая строка входного файла содержит число n ( 1 ≤ n ≤ 100000 ) количество котировок и k ( 1 ≤ k ≤ 10 ⁹ ). Вторая строка содержит n целых чисел последовательность котировок (все котировки находятся в интервале от 1 до 10 ⁹ включительно).

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

Первая строка выходного файла должна содержать l — длину оптимальной подпоследовательности. Вторая строка должна содержать l целых чисел элементы любой такой подпоследовательности.

Примеры

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

6 15
1014 1024 1034 1045 1030 998

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

4
1014 1045 1030 998

#112547

НЛО2

Темы: [Список]

Служба безопасности Земли хочет уничтожить корабль враждебно настроенных инопланетян. Служба безопасности уже повредила корабль и заставила его сесть в пустыне. Корабль построен из кубических отсеков единичного размера и нижний слой имеет форму прямоугольника размером N × M . На рисунке показан пример вида сверху на корабль размером N = 4 , M = 8 .

$\text{[math]}$ $\text{[math]}$

Отсеки корабля сделаны из сверхпрочного металла, поэтому для разрушения корабля используются лазеры. Лазерные установки были развернуты напротив четырех боковых сторон корабля, и они периодически выпускают лучи, перпендикулярные сторонам корабля, в сторону различных отсеков корабля. Каждый луч разрушает 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 ⁶ .

В следующих K строках описаны выстрелы из лазеров. Каждая из этих строк содержит один символ и через пробел от него число. Символы определяют сторону воздействия: "W" — запад, "E" — восток, "S" — юг, "N" — север. Число определяет номер строки в случае запада и востока или столбца в случае севера и юга. Строки и столбцы соответствуют нумерации из входных данных, слои нумеруются с единицы. Каждое число находится в диапазоне 1..10 ⁶ .

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

Выведите максимальное количество уцелевших отсеков после 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

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

#112555

Бег по эскалатору

Темы: [Алгоритмы сортировки] [Деревья]

Пусть N человек бегут вниз по эскалатору, причем i -ый пробегает одну ступеньку за t _i секунд. По технике безопасности бега по эскалатору, на эскалаторе запрещены "обгоны", то есть если A в процессе бега догнал человека B , который бежит с более низкой скоростью, то далее, до конца эскалатора, человек A бежит со скоростью человека B . Однако ступени эскалатора таковы, что на них может помещаться несколько человек одновременно. Ваша задача написать программу, которая рассчитает, когда закончит свой бег по эскалатору каждый бегущий человек.

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

В первой строке записано число N ( 1 ≤ N ≤ 10 ⁵ ). В следующих N строках перечислены пары чисел t _i , w _i ( 1 ≤ t _i , w _i ≤ 10 ⁶ )- время пробега одной ступени и количество ступеней до конца эскалатора. Гарантируется что изначально всем людям осталось бежать различное количество ступеней.

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

В i -ой строке выведите время в секундах, через которое i -ый человек сойдет с эскалатора

Примеры

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

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

20
33
33

#112567

Кубики

Темы: [Хеш] [Z-функция, Префикс-функция]

Привидение Петя любит играть со своими кубиками. Он любит выкладывать их в ряд и разглядывать свое творение. Однако недавно друзья решили подшутить над Петей и поставили в его игровой комнате зеркало. Ведь всем известно, что привидения не отражаются в зеркале! А кубики отражаются. Теперь Петя видит перед собой N цветных кубиков, но не знает, какие из этих кубиков настоящие, а какие — всего лишь отражение в зеркале. Помогите Пете! Выясните, сколько кубиков может быть у Пети. Петя видит отражение всех кубиков в зеркале и часть кубиков, которая находится перед ним. Часть кубиков может быть позади Пети, их он не видит.

$\text{[math]}$

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

Первая строка входного файла содержит число N ( 1 ≤ N ≤ 1000000 ) и количество различных цветов, в которые могут быть раскрашены кубики — M ( 1 ≤ M ≤ 1000000 ). Следующая строка содержит N целых чисел от 1 до M — цвета кубиков.

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

Выведите в выходной файл все такие K , что у Пети может быть K кубиков

Примеры

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

6 2
1 1 2 2 1 1

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

3 5 6