Height Queue (Fila de Alturas)
Você recebe uma fila de
n pessoas, em que cada pessoa tem uma altura representada por um inteiro positivo. É necessário processar q consultas, cada uma sendo um dos dois tipos a seguir:- Print Shorter People: Remover e imprimir as alturas de todas as pessoas na frente da fila cuja altura seja menor ou igual a um determinado valor
d, respeitando a ordem em que são removidas.
- Add Person: Adicionar uma pessoa com altura
dao final da fila.
Escreva um programa para processar essas consultas de forma eficiente.
Entrada
A primeira linha da entrada contém dois inteiros
n e q, que representam o número de pessoas inicialmente na fila e o número de consultas, respectivamente (1 ≤ n, q ≤ 100 000).A segunda linha contém
n inteiros , onde representa a altura da i-ésima pessoa na fila (1 ≤ ≤ ).Cada uma das próximas
q linhas representa uma consulta no formato:pop xpara uma consulta do tipo 1, em quexrepresenta a altura máxima permitida (1 ≤ x ≤ ).
add xpara uma consulta do tipo 2, em quexé a altura da pessoa que será adicionada ao final da fila (1 ≤ x ≤ ).
Saída
Para cada consulta do tipo 1, imprima as alturas das pessoas removidas na ordem em que saem da fila, separadas por espaços, em uma linha separada.
Entrada | Saída |
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
|
Explicação
A fila inicial contém cinco pessoas com alturas 5, 3, 8, 7 e 10, nessa ordem. As seis consultas são:
- pop 5: As duas primeiras pessoas na fila têm altura menor ou igual a 5, então são removidas da frente da fila e impressas em ordem, resultando na saída "5 3".
- add 4: Uma pessoa com altura 4 é adicionada ao final da fila.
- pop 9: As duas primeiras pessoas na fila têm altura menor ou igual a 9, então são removidas da frente da fila e impressas em ordem, resultando na saída "8 7".
- add 9: Uma pessoa com altura 9 é adicionada ao final da fila.
- pop 2: Todas as pessoas na fila têm altura maior que 2, então ninguém é removido da fila. A saída é uma linha vazia.
- pop 11: Todas as pessoas na fila têm altura menor ou igual a 11, então são removidas da frente da fila e impressas em ordem, gerando a saída "10 4 9".
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 10 MB