| Fişierul intrare/ieşire: | pixeli.in, pixeli.out | Sursă | RAUCoder 2020 |
| Autor | Daniela Alexandra Crisan | Adăugată de |  Daniela Alexandra Crisan •RAUCoder |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Pixeli
RAU-Gigel este pasionat de grafică, aşa că se gândeşte la un joc cu imagini. El creează într-un editor grafic o imagine bitmap binară de dimensiuni N X N pixeli. O imagine bitmap binară este o matrice de pixeli, fiecare pixel fiind un bit. Să considerăm că valoarea 0 (nesetat) înseamnă alb şi valoarea 1 (setat) înseamnă negru (în realitate este exact invers!). Apoi RAU-Gigel împarte imaginea în patru imagini pătrate egale de latură N / 2 pe care le notează de la 1 la 4 ( 1 este imaginea din colţul dreapta-sus, 2 este cea din colţul dreapta-jos, 3 stânga-jos şi 4 stânga-sus). El repetă procedeul pentru fiecare dintre cele 4 imagini obţinute, şi tot aşa, reducând mereu latura la jumătate şi notând direcţiile de la 1 la 4, până când ajunge la imagini de mărimea unui pixel.
Pentru simplitate, să presupunem că N este o putere a lui 2, să spunem K. Deci, după K împărţiri succesive de imagini, orice pixel poate fi identificat printr-un şir unic format din cifrele 1, 2, 3 şi 4, de lungime K.
De exemplu, dacă N = 4, atunci K = 2. Imaginea iniţială are 16 pixeli. Vom avea 2 împărţiri succesive:
După prima împărţire rezultă 4 imagini reduse la jumătate (fiecare are câte 4 pixeli):
4 1
3 2
După a doua împărţire rezultă 16 imagini de câte 1 pixel:
44 41 14 11
43 42 13 12
34 31 24 21
33 32 23 22
Iniţial, imaginea este complet albă.
Acum începe jocul. RAU-Gigel se gândeşte la 2 tipuri de operaţii:
Operaţia 1 x schimbă starea pixelul identificat cu şirul x, descris ca mai sus. Dacă pixelul x nu este setat, îl setează. Dacă pixelul x este deja setat, atunci îl resetează.
Operaţia 2 x , unde x are aceeaşi semnificaţie ca mai sus, este o interogare: dacă x este setat, se răspunde cu 0. Dacă x nu este setat, se cere determinarea dimensiunii celei mai mari imagini complet albe, dintre cele create de RAU-Gigel, care conţine pixelul x. Dimensiunea este dată de numărul de pixeli conţinut.
Dându-se N cu semnificaţia de mai sus şi M, reprezentând numărul de operaţii şi cele M operaţii de tipul 1 şi 2, să se răspundă la operaţiile de tip 2.
Date de intrare
Fişierul de intrare pixeli.in conţine pe prima linie numerele naturale N şi M separate cu un spaţiu. Pe următoarele M linii se află câte o cifră de 1 sau 2 şi câte un string, de forma tip_operaţie x, reprezentând tipul operaţiei şi şirul x.
Date de ieşire
Fişierul de ieşire pixeli.out va conţine răspunsurile pentru operaţiile de tip 2, câte unul pe linie.
Restricţii
- 2 ≤ N ≤ 2.000.000.000, 1 ≤ M ≤ 10.000
- In toate testele, N este o putere a lui 2
- Toate şirurile x sunt corect definite
- Pentru teste în valoare de 30 de puncte N <= 1.000 şi M <= 50
Exemplu
| pixeli.in | pixeli.out |
|---|---|
| 4 11 1 11 1 22 2 22 2 33 2 44 2 24 1 22 2 22 2 24 1 11 2 44 | 0 4 4 1 4 4 16 |
Explicaţie
Iniţial imaginea este albă:
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
După primele 2 operaţii de tip 1, imaginea va conţine:
0 0 0 1
0 0 0 0
0 0 0 0
0 0 0 1
Următoarele 4 interogări vor referi, în ordine, pixelii marcati cu a, b, c, d (imaginea de mai jos). Cum a era setat, răspunsul este 0. Cea mai mare imagine albă, creată de RAU-Gigel, care conţine b, este colţul stânga jos cu 4 pixeli. La fel pentru c. În cazul pixelului d, răspunsul este 1 (chiar el).
c 0 0 e
0 0 0 0
0 0 d 0
b 0 0 a
Urmează o operaţie de tip 1 care resetează pixelul notat cu a (şirul 22). Următoarele 2 interogări pentru a şi d generează răspunsurile 4, respectiv 4.
În final, se resetează şi pixelul e, iar ultima interogare, pentru c, va determina răspunsul 16, toată imaginea fiind acum complet albă.
