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
5 100 3
1 2 68 0 100
2 2 68
3 1 5 1 99
68

Explicatie

Miruna are 5 nepoti, oua de 100 de tipuri si efectueaza 3 operatii. La prima operatie nepotul 2 primeste 100 de oua de tip 68 si culoare 0. La a doua operatie nepotul 2 vopseste cele 100 de oua de tipul 68 pe care le are in culoarea 1. La a treia operatie Miruna vede ca al 99-lea cel mai gustos ou de culoare 1 pentru nepotii din intervalul [1, 5] are tipul 68.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content