Algorithmes et Structures de Données

File de hauteurs

On vous donne une file de n personnes, où chaque personne a une taille représentée par un entier positif. Vous devez traiter q requêtes, chacune appartenant à l'un des deux types suivants :
  1. Print Shorter People (Imprimer les personnes plus petites) : Retirez et affichez, dans l'ordre où elles sont retirées, toutes les personnes en début de file dont la taille est inférieure ou égale à une certaine valeur d.
  1. Add Person (Ajouter une personne) : Ajoutez une personne de taille d à la fin de la file.
Écrivez un programme pour traiter efficacement ces requêtes.

Entrée

La première ligne de l'entrée contient deux entiers n et q, qui représentent respectivement le nombre initial de personnes dans la file et le nombre de requêtes (1 ≤ n, q ≤ 100 000).
La deuxième ligne contient n entiers , où est la taille de la i-ème personne dans la file (1 ≤ ≤ ).
Chacune des q lignes suivantes décrit une requête, sous l'une des formes suivantes :
  • pop x si c’est une requête du premier type, où x représente la taille maximale autorisée (1 ≤ x ≤ ).
  • add x si c’est une requête du second type, où x est la taille de la personne à ajouter à la fin de la file (1 ≤ x ≤ ).

Sortie

Pour chaque requête du premier type, affichez sur une ligne distincte les tailles des personnes retirées, dans l’ordre où elles sont sorties de la file, séparées par des espaces.
Entrée
Sortie
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

Explication

La file initiale contient cinq personnes de taille 5, 3, 8, 7 et 10, dans cet ordre. Les six requêtes sont :
  1. pop 5 : Les deux premières personnes (taille 5 et 3) sont inférieures ou égales à 5, donc elles sont retirées et affichées dans l'ordre, ce qui donne "5 3".
  1. add 4 : Une personne de taille 4 est ajoutée à la fin de la file.
  1. pop 9 : Les deux premières personnes (taille 8 et 7) sont inférieures ou égales à 9, donc elles sont retirées et affichées dans l'ordre, ce qui donne "8 7".
  1. add 9 : Une personne de taille 9 est ajoutée à la fin de la file.
  1. pop 2 : Toutes les personnes restantes ont une taille supérieure à 2, donc personne n'est retiré et la ligne de sortie est vide.
  1. pop 11 : Toutes les personnes dans la file (10, 4, 9) sont inférieures ou égales à 11, donc elles sont retirées et affichées, ce qui donne "10 4 9".
 

Constraints

Time limit: 3 seconds

Memory limit: 512 MB

Output limit: 10 MB

To check your solution you need to sign in
Sign in to continue