АВТ
Язык:

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

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

695. I - близкие числа

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

При разработке системы анализа данных потребовалось решить следующую частную задачу. Имеется множество целых чисел (вначале пустое) и дана последовательность запросов трёх типов:

ADD x — добавить элемент x во множество (если такой элемент уже есть, то множество не изменяется)

DEL x — удалить элемент x из множества (если такого элемента нет, то множество не изменяется)

FIND — найти и вывести расстояние между двумя самыми близкими элементами в множестве. При этом гарантируется, что в множестве имеется не менее двух элементов.

Требуется выполнить заданную последовательность запросов.

Первая строка входного файла содержит одно целое число N (1 <= N <= 100 000) — общее количество запросов. В каждой из следующих N строк записан один запрос согласно приведённому выше формату. Все числовые значения в запросах лежат в диапазоне от 1 до 1 000 000 000.

Выведите в выходной файл по одному числу в строке для каждого запроса типа FIND — расстояние между двумя наиболее близкими элементами в множестве на момент выполнения запроса.

Пример

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

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

7

ADD 1

ADD 5

ADD 4

ADD 6

FIND

DEL 5

FIND

1

2

 

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи по темам / Динамические структуры данных /
695. 840. Pair multiply 1063. RMQ 253. Луч
Учебные курсы / Структуры и алгоритмы / Структуры данных /
695. 840. Pair multiply 228. Битовый массив 245. Делители
Задачи с соревнований / Межвузовские олимпиады / XII Межвузовская олимпиада 2009 /
694. H - игра 695. 696. Z - ровные делители (с пробного тура) 693. G - Кольцевой маршрут
 
время генерации 0.079 сек.
© Copyright ВоГУ, АВТ, Носов Д.А.