Algoritmos e Estruturas de Dados

Número de trocas realizadas pelo Heapify

Dado um heap inicialmente vazio, é solicitado que execute q consultas. Existem 2 tipos de consultas:
  1. add x - deve adicionar x ao heap
  1. pop - deve remover a raiz do heap
Para cada uma dessas consultas, é necessário imprimir o número de trocas (swaps) que ocorrem para reestruturar o heap, garantindo que a propriedade de max-heap seja mantida.
No caso das consultas pop, a troca entre a raiz e o último elemento também é contabilizada como uma troca.

Entrada

A primeira linha da entrada contém um único inteiro q (1 ≤ q ≤ ).
As próximas q linhas contêm as consultas, cada uma em sua própria linha. É garantido que, em todas as consultas do tipo add, o valor de x não excede em valor absoluto.

Saída

O programa deve imprimir o número de trocas para cada consulta, cada valor em uma linha separada.

Exemplos

Input
Entrada
7 add 1 add 2 add -3 add 4 pop add -2 pop
7 add 1 add 2 add -3 add 4 pop add -2 pop
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue