Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Вам требуется реализовать структуру данных, выполняющую следующие операции:
- Добавить элемент x в конец структуры.
- Удалить последний элемент из структуры.
- Выдать минимальный элемент в структуре.
В первой строке входного файла задано одно целое число n - количество операций ( 1 ≤ n ≤ 10^6 ). В следующих n строках заданы сами операции. В i –ой строке число ti - тип операции (1, если операция добавления. 2, если операция удаления. 3, если операция минимума). Если задана операция добавления, то через пробел записано целое число x - элемент, который следует добавить в структуру (− 10^9 ≤ x ≤ 10^9 ). Гарантируется, что перед каждой операцией удаления или нахождения минимума структура не пуста.
Для каждой операции нахождения минимума выведите одно число - минимальный элемент в структуре. Ответы разделяйте переводом строки.
Входные данные
8
1 2
1 3
1 -3
3
2
3
2
3
Выходные данные
-3
2
2
Ограничение по времени на тест: 1 секунда
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
В постфиксной записи (или обратной польской записи) операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как A B +. Запись B C + D ∗ обозначает привычное нам (B + C) ∗ D, а запись A B C + D ∗ + означает A + (B + C) ∗ D. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения. Дано выражение в обратной польской записи. Определите его значение.
В единственной строке записано выражение в постфиксной записи, содержащее однозначные числа и операции +,−,∗. Строка содержит не более 100 чисел и операций.
Необходимо вывести значение записанного выражения. Гарантируется, что результат выражения, а также результаты всех промежуточных вычислений по модулю меньше 2^31.
Входные данные
8 9 + 1 7 - * -
Выходные данные
-102
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Для каждой операции изъятия элемента выведите ее результат.
На вход программе подаются строки, содержащие команды. Каждая строка содержит одну команду. Команда — это либо "+ N", либо "-". Команда "+ N" означает добавление в очередь числа N, по модулю не превышающего 10^9. Команда "-" означает изъятие элемента из очереди.
В первой строке содержится количество команд — m (1⩽ m ⩽10^5). В последующих строках содержатся команды, по одной в каждой строке.
Выведите числа, которые удаляются из очереди, по одному в каждой строке. Гарантируется, что изъятий из пустой очереди не производится.
Входные данные
4
+ 1
+ 10
-
-
Выходные данные
1
10
Ограничение по времени на тест: 3 секунды
Ограничение по памяти на тест: 256 мегабайт
ввод: стандартный ввод
вывод: стандартный вывод
Реализуйте приоритетную очередь. Ваша очередь должна поддерживать следующие операции: добавить элемент, извлечь минимальный элемент, уменьшить элемент, добавленный во время одной из операций.
Если какой-нибудь decrease-key уменьшает уже удаленный элемент, то ничего делать не нужно.
Все операции нумеруются по порядку, начиная с 1.
Содержится описание операций со очередью. В очередь помещаются и извлекаются только целые числа, не превышающие 10^9 по абсолютной величине.
Гарантируется, что для любого decrease-key x v из входных данных операция под номером x является push.
Выведите последовательно результат выполнения всех операций extract-min из двух целых чисел: значение элемента и номер операции push, при котором этот элемент был добавлен. Если в очереди есть несколько минимальных элементов, выведите любой. Если перед очередной операцией extract-min очередь пуста, выведите звездочку.
Входные данные
push 3
push 4
push 2
extract-min
decrease-key 2 1
extract-min
extract-min
extract-min
Выходные данные
2 3
1 2
3 1
*