Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-06-04 09:08:38.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:kinder.in, kinder.outSursăLot 2008 - Piatra Neamt, Baraj2
AutorAndrei GrigoreanAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test1.5 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Kinder

Bunicuta Miruna are N nepotei care sunt asezati in linie si sunt numerotati de la stanga spre dreapta, in ordine, cu numere naturale distincte de la 1 la N. Deoarece se apropie Ziua Copilului, Miruna le-a cumparat nepoteilor mai multe oua Kinder. Aceste oua Kinder nu sunt toate la fel, ci sunt de M tipuri (numerotate de la 1 la M) si doua culori ( 0 - rosu si 1 - albastru). Tipul oului precizeaza cat de gustos este oul (daca tipul t1<t2, atunci un ou de tipul t1 va fi mai gustos decat un ou de tipul t2). Miruna va efectua operatii de urmatoarele 3 tipuri:

TipNumeFormatEfect
1Updatec t p qCopilul c primeste q oua de tip t si culoare p
2Updatec tCopilul c ia fiecare ou de tipul t care este al sau si il vopseste in culoarea opusa (din 0 in 1 si din 1 in 0)
3Querya b p xMiruna se uita la ouale de culoare p care apartin copiilor din intervalul [a, b] si vrea sa afle tipul celui de-al x-lea cel mai gustos ou.

Scrieti un program care sa efectueze in mod eficient toate operatiile descrise.

Date de intrare

Fisierul de intrare kinder.in va contine pe prima linie 3 numere naturale N M T, reprezentand numarul de nepotei, numarul de tipuri de oua, respectiv numarul de operatii ce vor fi efectuate. Pe fiecare dintre urmatoarele T linii va fi descrisa cate o operatie. Linia care descrie o operatie incepe cu un numar ($1$, 2 sau 3) care indica tipul operatiei, urmat de 4, 2, respectiv 4 numere naturale conform formatului operatiei. Valorile scrise pe aceeasi linie sunt separate prin spatiu.

Date de iesire

Fisierul de iesire kinder.out va contine cate o linie pentru fiecare operatie de tip 3 efectuata. Pe linia i se afla raspunsul pentru cea de a i-a operatie de tip 3 din fisierul de intrare.

Restrictii

  • 1 ≤ N, M, T ≤ 50000
  • Pentru operatii de tipul 1: 1 ≤ c ≤ N, 1 ≤ t ≤ M, 0 ≤ p ≤ 1, 1 ≤ q ≤ 1000
  • Pentru operatii de tipul 2: 1 ≤ c ≤ N, 1 ≤ t ≤ M
    Se garanteaza ca nepotul c are cel putin un ou de tip t
  • Pentru operatii de tipul 3: 1 ≤ a ≤ b ≤ N, 0 ≤ p ≤ 1
    1 ≤ x ≤ Numarul total de oua de culoare p pe care le detin nepotii din intervalul [a, b]
    Se garanteaza ca nepotii din intervalul [a,b] detin cel putin un ou de culoare p.

Exemplu

kinder.inkinder.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicatie

...

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?