Nombre d’échanges effectués par Heapify
Étant donné qu’au départ le tas (heap) est vide, vous devez exécuter
q requêtes. Il existe 2 types de requêtes :add x– doit ajouterxau tas
pop– doit supprimer la racine du tas
Pour chacune de ces requêtes, vous devez afficher le nombre d’échanges nécessaires afin de réorganiser le tas pour qu’il respecte la propriété de max-heap (tas maximum).
Pour les opérations
pop, l’échange entre la racine et le dernier élément est également comptabilisé comme un échange.Input
La première ligne de l’entrée contient un entier
q (1 ≤ q ≤ ).Les
q lignes suivantes contiennent les requêtes, chacune sur sa propre ligne. Il est garanti que, pour toutes les requêtes add, la valeur de x ne dépasse pas en valeur absolue.Output
Le programme doit imprimer le nombre d’opérations d’échange, chacune sur une nouvelle ligne.
Examples
Entrée | Sortie |
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