Fişierul intrare/ieşire:pixeli.in, pixeli.outSursăRAUCoder 2020
AutorDaniela Alexandra CrisanAdăugată deRAUCoderDaniela Alexandra Crisan RAUCoder
Timp execuţie pe test0.025 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/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.inpixeli.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ă.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?