Cola de Alturas
Se te proporciona una cola de
n personas, en la que cada persona tiene una altura representada por un número entero positivo. Debes procesar q consultas, cada una de las cuales es de uno de los siguientes dos tipos:- Imprimir personas más bajas: Remueve y muestra las alturas de todas las personas al frente de la cola cuya altura sea menor o igual a un valor
d, en el orden en que se van extrayendo.
- Agregar persona: Agrega al final de la cola una persona con altura
d.
Escribe un programa para procesar estas consultas de manera eficiente.
Entrada
La primera línea de la entrada contiene dos números enteros
n y q, que indican la cantidad de personas en la cola inicial y el número de consultas, respectivamente (1 ≤ n, q ≤ 100 000).La segunda línea contiene
n números enteros , donde representa la altura de la i-ésima persona en la cola (1 ≤ ≤ ).Cada una de las siguientes
q líneas representa una consulta de la forma:pop xsi se trata de una consulta de tipo 1, dondexes la altura máxima permitida (1 ≤ x ≤ ).
add xsi se trata de una consulta de tipo 2, dondexes la altura de la persona que se añadirá al final de la cola (1 ≤ x ≤ ).
Salida
Para cada consulta de tipo 1, muestra las alturas de las personas extraídas en el orden en que se extraen, separadas por espacios, en una línea independiente.
Entrada | Salida |
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
|
Explicación
La cola inicial contiene cinco personas con alturas 5, 3, 8, 7 y 10, en ese orden. Las seis consultas son las siguientes:
- pop 5: Las dos primeras personas de la cola tienen alturas menores o iguales a 5, así que se extraen del frente y se muestran en orden, dando como resultado "5 3".
- add 4: Se agrega una persona con altura 4 al final de la cola.
- pop 9: Las dos primeras personas de la cola tienen alturas menores o iguales a 9, por lo que se extraen y se muestran en orden, resultando en "8 7".
- add 9: Se agrega una persona con altura 9 al final de la cola.
- pop 2: Todas las personas en la cola tienen alturas mayores que 2, así que no se extrae ni se muestra a nadie. La salida es una línea vacía.
- pop 11: Todas las personas en la cola tienen alturas menores o iguales a 11, de modo que se extraen y se muestran en orden, resultando en "10 4 9".
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 10 MB