Fişierul intrare/ieşire:	petic.in, petic.out	Sursă	ad-hoc
Autor	Alexandru Petrescu	Adăugată de	descarc •arhive
Timp execuţie pe test	5 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Petic

Se da o matrice binara cu linii de la 0 la nrLin - 1 si coloane de la 0 la nrCol - 1, respectiv Q intrebari independente, de forma X₁ Y₁ X₂ Y₂: "Sa presupunem ca schimbam in 0 totii bitii de 1 din submatricea cu coltul stanga-sus pe linia X₁ si coloana Y₁ si coltul dreapta-jos pe linia X₂ si coloana Y₂. Care e numarul total de linii si coloane ale noii matrice care mai au macar un bit 1?"

Date de intrare

Fişierul de intrare petic.in contine, pe prima linie, numarele nrLin, nrCol si Q. Pe urmatoarele nrLin linii se afla cate un sir de nrCol biti. Pe urmatoarele Q linii se afla cate patru numere X₁ Y₁ X₂ Y₂.

Date de ieşire

În fişierul de ieşire petic.out se afla raspunsurile la cele Q intrebari, in ordine, cate un numar pe linie.

Restricţii

• Se recomanda parsarea intrarii si iesirii!
• 0 ≤ X₁ ≤ X₂ < nrLin
• 0 ≤ Y₁ ≤ Y₂ < nrCol
• nrLin ≤ nrCol
• 1 ≤ Q

Punctare

Subtask de 3 puncte

• nrCol ≤ 100
• Q ≤ 1.000

Subtask de 11 puncte

• nrCol ≤ 400
• Q ≤ 100.000

Subtask de 23 de puncte

• Toate submatricele din intrebari sunt patratice (X₂ - X₁ = Y₂ - Y₁)
• nrCol ≤ 1.000
• Q ≤ 1.000.000

Subtask de 24 de puncte

• Toate submatricele din intrebari sunt patratice (X₂ - X₁ = Y₂ - Y₁)
• nrCol ≤ 1.800
• Q ≤ 1.500.000

Subtask de 26 de puncte

• Q, nrLin * nrCol ≤ 400.000

Subtask de 13 puncte

• nrLin * nrCol ≤ 3.240.000
• Q ≤ 1.500.000

Exemplu

petic.in	petic.out
2 2 5 11 01 0 0 1 1 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1	0 3 4 4 3
2 3 8 100 111 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 2 0 1 0 1 1 1 1 1 0 2 0 2 1 2 1 2	2 4 5 3 5 4 5 4
1 2 1 01 0 0 0 1	0

Cum se trimit solutii?