Fişierul intrare/ieşire:undo2.in, undo2.outSursăONI 2016, clasa a 10-a
AutorPetru TrimbitasAdăugată deatatomirTatomir Alex •atatomir
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Undo2

XORin este nemulţumit de problemele primite în prima zi de concurs de la Olimpiada Naţională de Informatică şi decide astfel să se implice în comisie. În scurt timp devine specialistul comisiei în generarea de teste formate din şiruri de numere. Din când în când el trebuie să adauge sau să şteargă elemente din şir. Câteodată el decide să readauge dintre elemente şterse anterior. Fie şirul de numere a = (a 1 , a 2 , ... ,a N ) şi N numărul de elemente din şir după fiecare operaţie.
Astfel el are de realizat următoarele operaţii pornind de la un şir vid:

  • Inserează la sfârşitul şirului o valoare x;
  • Şterge ultimele x elemente din şir;
  • Readaugă la sfârşitul şirului primele x elemente şterse. Dacă, de exemplu, în operaţia anterioară de ştergere a unui număr y de elemente, am şters elementele a N-y+1 , a N-y+2 ,..., a N , iar acum urmează o operaţie de readăugare a x elemente, vor fi adăugate în ordine elementele a N-y+1 , a N-y+2 ,..., a N-y+x la sfârşitul şirului.

Din când în când XORin îşi pune următoarea întrebare: de câte ori există valoarea x în şir?

Date de intrare

Pe prima linie a fişierului undo2.in se va afla M ce reprezintă numărul de operaţii.
Pe următoarele M linii se vor afla operaţiile codificate astfel:
1 x - se inserează elementul x la sfârşitul şirului
2 y - se şterg ultimele y elemente adăugate în şir
3 z - se adaugă înapoi la sfârşitul şirului primele z elemente şterse
4 t - se afişează numărul de elemente cu valoarea t din şir

Date de ieşire

Pe fiecare linie a fişierului undo2.out se scriu răspunsurile la întrebările lui XORin, fiecare răspuns pe câte o linie.

Restricţii

  • Toate numerele din fişierul de intrare sunt cuprinse între 1 şi 200 000;
  • Pentru 20% din teste se garantează M ≤ 1 000, pentru alte 40% din teste, se garantează că numerele inserate vor fi distincte;
  • Între o operaţie de readăugare si operatia anterioară de stergere nu vor exista operatii de inserare.
  • Numărul de elemente readăugate nu va fi mai mare decât numărul de elemente şterse la ultima operaţie.
  • Între două operaţii de readăugare va exista cel puţin o operaţie de ştergere.

Exemplu

undo2.inundo2.outExemplu
16
1 1
1 2
1 3
1 4
4 4
2 2
4 3
3 1
4 4
4 3
1 7
1 7
1 7
4 7
2 2
4 7
1
0
0
1
3
1
Iniţial şirul este vid.
După primele 4 operaţii de inserare şirul este 1, 2, 3, 4.
Operaţia 4 4 va afişa 1.
Operaţia 2 2 va şterge ultimele două elemente şirul devenind 1, 2.
Din cauză că elementul 3 a fost şters, a şaptea operaţie va afişa 0.
Operaţia 3 1 va readăuga la sfârşitul şirului elementul 3.
În urma acestei operaţii şirul devine 1, 2, 3.
Operaţia 4 4 va afişa 0, iar operaţia 4 3 va afişa 1.
ş.a.m.d.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?