Республиканская олимпиада по информатике 2009 год
Задача B. Фокус
Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт
Помните про фокус с мухами, который изобрел Баха? Жома решил посоревноваться с ним и придумал свой фокус! У Жомы есть ящик. Он может запускать туда муху или выпускать. Также, он как хороший дрессировщик знает возраст каждой мухи в минутах с момента ее рождения. А фокус заключается вот в чем: в любой момент он может назвать возраст $K$-й по старшинству мухи, которая находится в ящике среди мух с возрастом от $A$ до $B$ включительно. Попробуйте и вы сделать этот фокус!
Формат входного файла
Первая строка входного файла содержит число $N$ — общее количество событий ($1 \le N \le 2 \cdot 10^5$). Далее следует $N$ строк, каждая из которых описывает одно из событий:
- $+ X$ — в ящик впустили муху с возрастом $X$;
- $- X$ — из ящика выпустили муху с возрастом $X$;
- $? K A B$ — у фокусника спросили возраст $K$-й по старшинству мухи в ящике среди мух с возрастом от $A$ до $B$ включительно ($1 \le K \le 10^5$, $A \le B$);
Формат выходного файла
Выходной файл должен содержать такое же количество строк, сколько запросов возраста было во входном файле. Для каждого такого запроса нужно вывести строку, содержащую соответствующее число — ответ на запрос. При этом, если при количество мух с возрастом от $A$ до $B$ в ящике меньше $K$, то нужно вывести $0$.
Пример:
Вход 8 + 2 + 3 + 2 ? 2 2 3 - 2 ? 2 2 3 - 2 ? 2 2 3Ответ
2 3 0
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.