Fișierul intrare/ieșire | pasari.in, pasari.out | Sursă | ad-hoc |
---|---|---|---|
Autor | Cătălin Frâncu | Adăugată de | Cătălin Frâncu • Catalin.Francu |
Timp de execuție pe test | 0.2 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Păsări (clasele 11-12)
Un traseu turistic are N km lungime. La începutul lui se află punctul de informare turistică. În zonă migrează S specii de păsări, iar turiștii vin frecvent să le vadă. În decursul unui an se întâmplă K evenimente de două tipuri:
- O pasăre din specia s își contruiește cuibul la kilometrul x pe traseu.
- Un turist vine la punctul de informare și întreabă: „dacă fac un traseu de x km, câte specii distincte de păsări pot să văd?”
Ajutați-i pe ghizii turistici să răspundă eficient la întrebări.
Date de intrare
Fișierul de intrare pasari.in conține pe prima linie numerele N S K separate prin spații. Următoarele K linii descriu câte un eveniment în forma
- 1 s x – pentru evenimente de tipul 1
- 2 x – pentru evenimente de tipul 2
Date de ieșire
În fișierul de ieșire pasari.out se vor scrie atâtea linii câte evenimente de tipul 2 există. Fiecare linie va conține răspunsul la o întrebare, în ordinea întrebărilor.
Restricții
- 1 ≤ N ≤ 100.000
- 1 ≤ S ≤ 30
- 1 ≤ K ≤ 100.000
- 1 ≤ s ≤ S și 1 ≤ x ≤ N pentru toate evenimentele
Exemplu
pasari.in | pasari.out |
---|---|
7 3 6 1 1 3 1 2 5 2 6 1 3 5 1 1 3 2 3 |
2 1 |
Explicație
În momentul primei întrebări, la km 1 se află o pasăre din specia 1, iar la km 5 se află o pasăre din specia 2.
În momentul celei de-a doua întrebări, la km 3 se află două păsări din specia 1 (deci o singură specie distinctă).