СарварИбрагимов11

03.10.2022 13:05

Информатика

Есть ответ 👍

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