Implementazione di un Heap Personalizzato
Partendo da un heap inizialmente vuoto, si devono eseguire q operazioni (query). Esistono tre tipi di operazioni:
add x– inseriscexnell'heappop– rimuove la radice dell'heapmax– visualizza l'elemento massimo dell'heap
Input
La prima riga dell’input contiene un singolo intero q (1 ≤ q ≤ 10^5).
Le successive q righe contengono le operazioni, ciascuna su una riga separata. È garantito che, per tutte le istruzioni add, il valore di x non superi 10^9 in valore assoluto. È inoltre garantito che tutte le istruzioni siano valide e che non venga mai richiesto un pop se l’heap è vuoto.
Output
Il programma deve stampare i risultati corrispondenti a tutte le istruzioni max, ognuno su una nuova riga.
Examples
Input | Input |
|---|---|
9 add 1 add 2 max add -3 add 4 max add -2 pop max | 9 add 1 add 2 max add -3 add 4 max add -2 pop max |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB