Окружной этап Всероссийской олимпиады школьников по информатике, 2015, I тур Россия, Самара, 14 ноября 2015 Задача D. Трамвайная остановка Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение ...

Окружной этап Всероссийской олимпиады школьников по информатике, 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 — количество сообщений о проезжающих машинах).
Гость
Ответ(ы) на вопрос:
Гость
не хорошо олимпиады  с источников скатывать))0 Условия читал хоть?
Гость
Решение в прикрепленном файле.
Не нашли ответ?
Ответить на вопрос
Похожие вопросы