Höhen-Warteschlange
Sie haben eine Warteschlange von
n Personen, wobei jede Person eine durch eine positive ganze Zahl repräsentierte Körpergröße besitzt. Es gilt, q Abfragen (Queries) zu bearbeiten, die jeweils einer der folgenden zwei Typen angehören:- Print Shorter People: Entfernen Sie alle Personen aus dem Anfang der Warteschlange, deren Körpergröße kleiner oder gleich
dist, und geben Sie deren Größen in der Reihenfolge aus, in der sie entfernt werden.
- Add Person: Fügen Sie eine Person mit der Größe
dan das Ende der Warteschlange an.
Schreiben Sie ein Programm, das diese Abfragen effizient bearbeitet.
Eingabe
Die erste Zeile der Eingabe enthält zwei Ganzzahlen
n und q, die die Anzahl der Personen in der anfänglichen Warteschlange und die Anzahl der Abfragen angeben (1 ≤ n, q ≤ 100.000).Die zweite Zeile enthält
n Ganzzahlen , wobei die Körpergröße der i-ten Person in der Warteschlange repräsentiert (1 ≤ ≤ ).Jede der folgenden
q Zeilen beschreibt eine Abfrage in der Form:pop x, wenn es sich um eine Abfrage vom Typ 1 handelt, wobeixdie maximale zulässige Größe ist (1 ≤ x ≤ ).
add x, wenn es sich um eine Abfrage vom Typ 2 handelt, wobeixdie Größe der hinzuzufügenden Person ist (1 ≤ x ≤ ).
Ausgabe
Für jede Abfrage vom Typ 1 geben Sie die Höhen der entfernten Personen in der Reihenfolge aus, in der sie entfernt werden, getrennt durch Leerzeichen. Verwenden Sie für jede solche Abfrage eine eigene Zeile.
Eingabe | Ausgabe |
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
|
Erklärung
Die anfängliche Warteschlange enthält fünf Personen mit den Größen 5, 3, 8, 7 und 10 in dieser Reihenfolge. Die sechs Abfragen lauten wie folgt:
- pop 5: Die ersten beiden Personen in der Warteschlange haben Größen, die kleiner oder gleich 5 sind. Also werden sie aus dem Anfang der Warteschlange entfernt und in dieser Reihenfolge ausgegeben, was das Ergebnis "5 3" liefert.
- add 4: Eine Person mit Größe 4 wird ans Ende der Warteschlange angefügt.
- pop 9: Die ersten beiden Personen in der Warteschlange haben Größen, die kleiner oder gleich 9 sind, also werden sie entfernt und ausgegeben, was das Ergebnis "8 7" liefert.
- add 9: Eine Person mit Größe 9 wird ans Ende der Warteschlange angefügt.
- pop 2: Alle Personen in der Warteschlange sind größer als 2, daher wird niemand entfernt. Die Ausgabezeile bleibt leer.
- pop 11: Nun sind alle Personen in der Warteschlange kleiner oder gleich 11, sodass sie alle entfernt und der Reihe nach ausgegeben werden. Daher lautet die Ausgabe "10 4 9".
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 10 MB