Fişierul intrare/ieşire:petic.in, petic.outSursăad-hoc
AutorAlexandru PetrescuAdăugată de
Timp execuţie pe test10 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/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 X1 Y1 X2 Y2: "Sa presupunem ca schimbam in 0 totii bitii de 1 din submatricea cu coltul stanga-sus pe linia X1 si coloana Y1 si coltul dreapta-jos pe linia X2 si coloana Y2. 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 X1 Y1 X2 Y2.

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 ≤ X1 ≤ X2 < nrLin
  • 0 ≤ Y1 ≤ Y2 < 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 (X2 - X1 = Y2 - Y1)
  • nrCol ≤ 1.000
  • Q ≤ 1.000.000

Subtask de 24 de puncte

  • Toate submatricele din intrebari sunt patratice (X2 - X1 = Y2 - Y1)
  • 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.inpetic.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?