АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1992. Построение

Ограничение времени: 1 сек.
Ограничение памяти:262144 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

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

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

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

Первая строка входных данных cодержит число N – количество событий (1 ≤ N ≤ 105). В каждой следующей строке содержится описание события: числа 1 и X, если солдат приходит в строй (X – рост солдата, натуральное число до 100 000 включительно), и числа 2 и Y, если солдата, стоящего в строе на месте Y, надо удалить из строя (солдаты в строе нумеруются с нуля).

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

В выходной файл выведите в отдельной строке для каждой команды 1 (добавление в строй) число K – номер позиции, на которую должен встать этот солдат (все стоящие за ним двигаются назад).

Пример

Входные данные
5
1 100
1 200
1 50
2 1
1 150
Выходные данные
0
0
2
1

Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи по темам / Динамические структуры данных /
370. Пирамида 1992. 1975. Река 862. Стек 42. Считалочка
Учебные курсы / Алгоритмы и структуры данных / Структуры данных /
1981. Последняя вершина 1992. 248. Постфиксная запись 1984. Прибавления 1982. Присвоения
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, смена 2019 / Олимпиада закрытия /
1183. 11 - Цепочки знакомств 1992.
Задачи с соревнований / Школьные олимпиады Вологодской области / Импульс, сентябрь 2020 / Импульс-2020, олимпиада закрытия, группа 1 /
2038. 05 - Самый частый элемент 1992. 1434. 07 - Контроль скорости 176. 08 - Сообщение 1228. 09 - Наилучший путь
 
время генерации 0.109 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.