Número de intercambios realizados por Heapify
Dado que comienzas con un heap inicialmente vacío, se te solicita efectuar
q consultas. Existen 2 tipos de consultas:add x- debe agregarxal heap
pop- debe eliminar la raíz del heap
En cada una de las consultas, se te pide imprimir la cantidad de intercambios necesarios para reestructurar el heap de modo que cumpla con la propiedad de max-heap.
En las operaciones
pop, también se cuenta como intercambio (swap) el que ocurre entre la raíz y el último elemento.Entrada
La primera línea de la entrada contiene un entero
q (1 ≤ q ≤ ).Las siguientes
q líneas contienen consultas, cada una en una línea separada. Se garantiza que para todas las consultas de tipo add, el valor de x no sobrepasa en valor absoluto.Salida
El programa debe imprimir la cantidad de intercambios en cada línea, uno por cada consulta.
Ejemplos
Entrada | Salida |
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