Количество обменов (swaps), выполняемых при Heapify
Дана изначально пустая куча (heap). Требуется обработать
q запросов. Запросы бывают двух типов:add x— добавляетxв кучу
pop— удаляет корень кучи
Для каждого запроса необходимо вывести, сколько обменов пришлось сделать для перестройки кучи и сохранения свойства max-heap.
Обратите внимание, что в операции
pop обмен корня с последним элементом также считается за один обмен.Входные данные
Первая строка содержит одно целое число
q (1 ≤ q ≤ ).Следующие
q строк содержат запросы — по одному в каждой строке. Гарантируется, что при любом запросе add значение x не превосходит по модулю .Выходные данные
Программа должна вывести количество операций обмена, по одной на строку.
Пример
Входные данные | Выходные данные |
7
add 1
add 2
add -3
add 4
pop
add -2
pop | 0
1
0
2
2
0
2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB