Coda in base all'altezza
Ti viene fornita una coda di
n persone, dove ciascuna persona ha un'altezza rappresentata da un intero positivo. Devi gestire q interrogazioni, ognuna delle quali è di uno dei seguenti due tipi:- Stampa le persone più basse: Rimuovi e stampa le altezze di tutte le persone dal fronte della coda la cui altezza è minore o uguale a un certo valore
d, nell’ordine in cui vengono estratte.
- Aggiungi una persona: Aggiungi una persona con altezza
din fondo alla coda.
Scrivi un programma che esegua queste interrogazioni in modo efficiente.
Input
La prima riga dell'input contiene due interi
n e q, che indicano rispettivamente il numero di persone inizialmente presenti nella coda e il numero di interrogazioni (1 ≤ n, q ≤ 100 000).La seconda riga contiene
n interi , dove rappresenta l’altezza della i-esima persona nella coda (1 ≤ ≤ ).Ciascuna delle successive
q righe rappresenta un’interrogazione del formato:pop xse si tratta di un’interrogazione di tipo 1, dovexè l’altezza massima consentita (1 ≤ x ≤ ).
add xse si tratta di un’interrogazione di tipo 2, dovexè l’altezza della persona da aggiungere in fondo alla coda (1 ≤ x ≤ ).
Output
Per ogni interrogazione di tipo 1, stampa le altezze delle persone rimosse nell’ordine in cui vengono estratte, separate da uno spazio, ciascuna su una nuova riga.
Ingresso | Uscita |
5 6
5 3 8 7 10
pop 5
add 4
pop 9
add 9
pop 2
pop 11 | 5 3
8 7
10 4 9
|
Spiegazione
La coda iniziale contiene cinque persone con altezze 5, 3, 8, 7 e 10, in quest’ordine. Le sei interrogazioni sono le seguenti:
- pop 5: Le prime due persone nella coda hanno un’altezza minore o uguale a 5, quindi vengono rimosse dal fronte della coda e stampate nell’ordine, producendo in uscita "5 3".
- add 4: Una persona con altezza 4 viene aggiunta in fondo alla coda.
- pop 9: Le prime due persone nella coda hanno un’altezza minore o uguale a 9, quindi vengono rimosse dal fronte e stampate nell’ordine, producendo "8 7".
- add 9: Una persona con altezza 9 viene aggiunta in fondo alla coda.
- pop 2: Tutte le persone nella coda hanno un’altezza superiore a 2, quindi non viene rimossa nessuna persona e l’uscita è una riga vuota.
- pop 11: Tutte le persone nella coda hanno un’altezza minore o uguale a 11, quindi vengono rimosse dal fronte e stampate nell’ordine, producendo "10 4 9".
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 10 MB