Fişierul intrare/ieşire:pasari.in, pasari.outSursăad-hoc
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.2 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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:

  1. O pasăre din specia s îşi contruieşte cuibul la kilometrul x pe traseu.
  2. 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.inpasari.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ă).

Trebuie sa te autentifici pentru a trimite solutii. Click aici