Ալգորիթմներ և Տվյալների Կառուցվածքներ

Բարձրությունների հերթ

Ձեզ տրված է n անձանց հերթ, որտեղ յուրաքանչյուր մարդու բարձրությունը դրական ամբողջ թիվ է։ Պետք է մշակեք q հարցում, որոնցից յուրաքանչյուրը պատկանում է հետևյալ երկու տեսակներից մեկին.

  1. Տպել քիչ բարձրություն ունեցողներին: Հերթի առջևից հեռացրեք ու տպեք այն մարդկանց բարձրությունները, որոնց բարձրությունը փոքր կամ հավասար է որոշակի d արժեքի, պահպանելով նույն հերթականությունը, որով նրանք դուրս են գալիս հերթից:

  2. Ավելացնել մարդ: Հերթի վերջում ավելացրեք մի մարդու, որի բարձրությունը d է:

Գրեք ծրագիր, որը արդյունավետորեն կաշխատի նշված հարցումների հետ։

Մուտք

Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր n և q, որոնք սահմանում են նախնական հերթում գտնվող մարդկանց քանակը և հարցումների քանակը, համապատասխանաբար (1 ≤ n, q ≤ 100000)։

Մուտքի երկրորդ տողում տրված են n ամբողջ թվեր , որտեղ հանդիսանում է հերթում գտնվող i-րդ մարդու բարձրությունը (1 ≤ ≤ )։

Այնուհետև հաջորդ q տողերից յուրաքանչյուրում նկարագրվում է մեկ հարցում, որը կարող է լինել հետևյալ ձևերից մեկով.

  • pop x, եթե այն 1-ին տիպի հարցում է և x-ը սահմանում է թույլատրելի առավելագույն բարձրությունը (1 ≤ x ≤ )

  • add x, եթե այն 2-րդ տիպի հարցում է և x-ը այն բարձրությունն է, որ պետք է ավելացվի հերթի վերջում (1 ≤ x ≤ )

Ելք

Յուրաքանչյուր 1-ին տիպի հարցման համար պետք է տպել հերթից հեռացված մարդկանց բարձրությունները (եթե կան) հերթով բաժանված բացատներով, և ամեն խումբ տպել նոր տողի վրա:

Մուտք

Ելք

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

Բացատրություն

Սկզբում հերթում կա հինգ մարդ՝ 5, 3, 8, 7 և 10 բարձրություններով (նույն հերթականությամբ)։ Այնուհետև տրվում են վեց հարցումներ.

  1. pop 5: Քանի որ առաջին երկու մարդկանց բարձրությունը 5-ից փոքր կամ հավասար է, նրանք դուրս են գալիս հերթից և տպվում են ըստ հերթականության՝ "5 3":

  2. add 4: Հերթի վերջում ավելանում է բարձրությամբ 4 մարդ:

  3. pop 9: Առաջին երկու մարդիկ, որոնց բարձրությունը ≤ 9 է, դուրս են գալիս և տպվում ըստ հերթականության՝ "8 7":

  4. add 9: Հերթի վերջում ավելանում է բարձրությամբ 9 մարդ:

  5. pop 2: Հերթում գտնվող բոլոր մարդկանց բարձրությունը 2-ից մեծ է, ուստի ոչ ոք չի հեռացվում, տպագրությունը դատարկ տող է:

  6. pop 11: Հերթում գտնվող բոլոր մարդիկ ունեն բարձրություն ≤ 11, հետևաբար նրանք բոլորը դուրս են գալիս հերթից և տպվում են ըստ հերթականության՝ "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