Олимпиадный тренинг

Задача . F. Лена и запросы


Задача

Темы: Структуры данных геометрия разделяй и властвуй *2500

Лена — программист. На работе она получила задачу.

Рассмотрим некоторое, изначально пустое множество пар целых чисел. Лене нужно обработать n запросов одного из трёх типов:

  1. Добавить пару чисел (a, b) в множество.
  2. Удалить пару чисел, добавленную в i-м запросе. Все запросы пронумерованы целыми числами от 1 до n.
  3. Для заданного целого числа q найти максимальное значение величины x·q + y среди всех пар (x, y) из множества.

Помогите Лене обработать запросы.

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

В первой строке находится целое число n (1 ≤ n ≤ 3·105) — количество запросов.

Каждая из следующих n строк начинается с целого числа t (1 ≤ t ≤ 3) — типа очередного запроса.

Далее в запросах первого типа следует пара целых чисел a и b ( - 109 ≤ a, b ≤ 109).

В запросах второго типа следует целое число i (1 ≤ i ≤ n). Гарантируется, что число i меньше номера текущего запроса, i-й запрос первого типа и пара из i-го запроса ещё не удалена.

В запросах третьего типа следует целое число q ( - 109 ≤ q ≤ 109).

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

Для запросов третьего типа выведите в отдельной строке искомое максимальное значение x·q + y.

Если в множестве нет пар выведите "EMPTY SET".


Примеры
№Входные данныеВыходные данные
1 
7
3 1
1 2 3
3 1
1 -1 100
3 1
2 4
3 1
 
EMPTY SET
5
99
5

time 4000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++5
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет