Окружной этап Всероссийской олимпиады школьников по информатике, 2015, I тур
Россия, Самара, 14 ноября 2015
Задача D. Трамвайная остановка
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Прохор решил подождать Кешу на трамвайной остановке. Дождь уже прекратился, но после него
возле остановки образовалась огромная лужа, и теперь от каждой проезжающей машины разлета-
ются брызги. Прохор оглядел свое новенькое пальто, встал подальше от дороги и стал наблюдать
за происходящим.
Когда Прохор пришёл на остановку, на ней уже стояли n человек. Для каждого из них известно
расстояние от края тротуара s1, s2, . . . , sn. Среди этих расстояний можно выделить smin = min
i=1..n
{si}
и smax = max
i=1..n
{si}. Когда приходит новый потенциальный пассажир, он сразу обращает внимание
на лужу, и встает от неё на расстоянии, равном (smin+smax)/2 (округление выполняется в меньшую
сторону).
Прохор заметил, что каждая машина (#j) характеризуется параметром dj — расстоянием от
края тротуара, на которое долетают брызги. Всех, кто стоит ближе dj , окатывает брызгами, после
чего они, отряхиваясь и негромко произнося слова глубокой благодарности в адрес водителя, отходят
на расстояние dj + 1 от края тротуара и ближе уже не подходят. Разумеется, эти перемещения могут
повлиять на значения smin и smax, и очередной потенциальный пассажир, пришедший после проезда
очередной машины, будет определять для себя расстояние от края тротуара, исходя из этих новых
значений.
По данным о приходящих потенциальных пассажирах и проезжающих машинах определите для
каждой машины, сколько людей, ожидающих транспорт, удалось обрызгать её водителю.
Формат входных данных
В первой строке содержатся целые положительные числа n и q (1 ⩽ (n+q) ⩽ 3·105
) — начальное
количество людей, ожидающих транспорт, на остановке и количество сообщений о приходящих
потенциальных пассажирах и проезжающих машинах.
Во второй строке содержится n целых чисел s1, s2, . . . , sn (0 ⩽ sj ⩽ 109
) — расстояния от края
тротуара, на которых исходно стоят потенциальные пассажиры.
В каждой из следующих q строк содержится сообщение одного из двух видов:
— единственный символ p, обозначающий, что на остановку пришёл потенциальный пассажир;
— символ c, обозначающий, что мимо остановки проехала машина, и целое число dj
(0 ⩽ dj ⩽ 109
) — расстояние от края тротуара, на которое долетают брызги от этой машины.
Гарантируется, что во входных данных есть информация о хотя бы одной проехавшей машине.
Формат выходных данных
В единственной строке выведите z целых чисел y1, y2, . . . , yz, где yj — количество людей, которых
удалось обрызгать водителю машины #j (z — количество сообщений о проезжающих машинах).