Fișierul intrare/ieșire pasari.in, pasari.out Sursă ad-hoc
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu 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 stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.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ă).

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii