Fișierul intrare/ieșire	nisip.in, nisip.out	Sursă	ONI 2023, Clasa a 9-a
Autor	OSEPI	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	0.6 sec	Limită de memorie	16384 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

Nisip (Clasa a 9-a)

Loid Forger a primit o nouă misiune: să saboteze o mină importantă de lângă Berlint, Ostania. Mina are forma unei coloane verticale împărțită pe n niveluri, numerotate de la 1 (cel mai de sus nivel) la n (cel mai de jos). Fiecare nivel conține aer (care are codul 0), nisip (care are codul 1) sau piatră (care are codul 2).

Misiunea lui Loid constă în a dinamita piatra de pe unele niveluri pentru a provoca surparea minei și curgerea nisipului spre nivelurile inferioare. El are de îndeplinit m sarcini numerotate de la 1 la m. Acestea sunt de două tipuri:

• 1 t p (dinamitare): Loid trebuie ca, la secunda t, să dinamiteze piatra de pe nivelul p al minei. Pentru orice astfel de sarcină, Loid știe că, la secunda t, nivelul p conține piatră, iar aceasta va fi înlocuită de aer la secunda t + 1, după dinamitare.
• 2 t p (întrebare): Pentru a i se testa perspicacitatea, Loid este întrebat ce conține nivelul p al minei la secunda t: aer, nisip sau piatră?

În general, conținutul unui nivel la secunda t va fi același și la secunda t + 1, cu două excepții:

• Curgerea nisipului: dacă, la secunda t, nivelul p conține nisip și nivelul p + 1 conține aer, nisipul va curge și, la secunda t + 1, nivelul p conține aer și nivelul p + 1 conține nisip.
• Dinamitarea de către Loid: un nivel care conține piatră și este dinamitat la secunda t va conține aer la secunda t + 1.

Dacă, la secunda t, fiecare nivel i de la 1 la n al minei are același conținut ca la secunda t − 1, spunem că mina este stabilă la secunda t.

Cerință

Dându-se n, conținuturile tuturor nivelurilor minei la secunda 0, m și sarcinile care trebuie îndeplinite, să se determine răspunsurile la sarcinile de tip întrebare.

Date de intrare

Fișierul de intrare nisip.in va conține pe prima linie două numere naturale n și m separate printr-un spațiu, reprezentând numărul de niveluri ale minei, respectiv numărul de sarcini.

Pe următoarea linie se vor afla n numere naturale separate prin câte un spațiu, al i-lea dintre acestea reprezentând codul conținutul nivelului i al minei (0 pentru aer, 1 pentru nisip, 2 pentru piatră).

Următoarele m linii conțin descrierile sarcinilor din cadrul misiunii lui Loid. A i-a dintre acestea va conține trei numere naturale ci, ti și pi separate printr-un spațiu, reprezentând, în ordine cronologică, sarcinile date lui Loid: ci reprezintă tipul
sarcinii i ( 1 pentru dinamitare, 2 pentru întrebare), ti reprezintă secunda și pi reprezintă nivelul minei.

Date de ieșire

Fișierul de ieșire nisip.out conține codurile corespunzătoare răspunsurilor la sarcinile de tip întrebare (0 pentru aer, 1 pentru nisip, 2 pentru piatră), în ordinea din fișierul de intrare, câte unul pe fiecare linie.

Restricții

• 1 ≤ n ≤ 1 000 000
• 1 ≤ m ≤ 1 000 000
• 1 ≤ ti ≤ 1 000 000 000 și 1 ≤ pi ≤ n pentru orice i, 1 ≤ i ≤ m.
• ti < ti+1, pentru orice i, 1 ≤ i < m.
• Nivelul n conține întotdeauna piatră și Loid nu va avea niciodată sarcina de a dinamita piatra de pe nivelul n.
• Mina este stabilă la secunda 1.
• Pentru fiecare sarcină i pentru care ci = 1, mina este stabilă la secunda ti

Punctaj

	Punctaj	Restricții
1	21	n ≤ 1 000, m ≤ 1 000, ti ≤ 3 000, pentru orice i, 1 ≤ i ≤ m.
2	28	c1 = 1, ci = 2, pentru orice i, 2 ≤ i ≤ m.
3	22	Există maximum 1 000 de niveluri care conțin nisip și maximum 1 000 de sarcini de tipul 1.
4	29	Fără restricții suplimentare.

Mențiune

Rezultatele evaluării pot fi diferite față de cele din concurs.

Exemplu

nisip.in	nisip.out
6 4 0 1 1 2 0 2 1 1 4 2 2 3 2 4 2 2 5 4	1 0 1

Explicație

Conținuturile nivelurilor minei sunt:

• 0 1 1 2 0 2 la secunda 1,
• 0 1 1 0 0 2 la secunda 2,
• 0 1 0 1 0 2 la secunda 3,
• 0 0 1 0 1 2 la secunda 4,
• 0 0 0 1 1 2 la secunda 5,
• 0 0 0 1 1 2 la secunda 6, etc.