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

Задача . E. Максимизируй!


Задача

Темы: Бинарный поиск два указателя жадные алгоритмы Тернарный поиск *1800

Дано мультимножество S из натуральных чисел, изначально пустое. С ним производятся операции двух типов:

  1. Добавить в S натуральное число, не меньшее всех уже лежащих в множестве элементов.
  2. Найти непустое подмножество s множества S такое, что значение максимально. Здесь max(s) обозначает максимум среди всех элементов s,  — среднее арифметическое всех элементов s. Вывести величину .
Входные данные

В первой строке задано единственное натуральное число Q (1 ≤ Q ≤ 5·105) — количество операций. В каждой из следующих Q строк следует описание очередной операции. Для операций типа 1 в строке будут записаны два числа вида 1 и x, где x (1 ≤ x ≤ 109) — число, которое нужно добавить в S. Гарантируется, что x будет не меньше любого элемента S на данный момент. Для операции типа 2 в соответствующей строке будет записано ровно одно число 2.

Гарантируется, что первая операция будет иметь тип 1, то есть множество S не будет пустым при поступлении операций типа 2.

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

Выведите ответ на каждую операцию второго типа в том порядке, в котором эти операции шли во входных данных. Каждое число должно располагаться на отдельной строке.

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

Формально, пусть ваш ответ равен a, а ответ жюри — b. Ваш ответ будет считаться правильным, если .


Примеры
№Входные данныеВыходные данные
1 6
1 3
2
1 4
2
1 8
2 
0.0000000000
0.5000000000
3.0000000000
2 4
1 1
1 4
1 5
2 
2.0000000000

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

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

Ваш ответ

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


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

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