Fişierul intrare/ieşire:camere.in, camere.outSursăLot 2017 Baraj 1
AutorLucian Bicsi, Radu MunteanAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test1.5 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Camere

Se dă o matrice de N linii şi M coloane care conţine numai litere mici ale alfabetului englez. Se defineşte o cameră ca o zonă maximală de celule din matrice ce conţin aceeaşi literă, conexă pe cele 4 direcţii: sus, jos, stânga, dreapta.

Ne interesează răspunsuri la întrebări de forma: “Câte camere sunt incluse complet sau parţial într-un dreptunghi dat, văzut ca o submatrice?”.

Date de intrare

Pe prima linie a fişierului de intrare camere.in se vor afla 2 numere N şi M separate prin câte un spaţiu, iar pe următoarele N linii câte M caractere din alfabetul englez (neseparate prin spaţii). Linia N+2 va conţine un număr Q, reprezentând numărul de întrebări, iar următoarele Q linii vor conţine câte 4 numere x1, y1, x2, y2 separate prin câte un spaţiu, reprezentând câte un dreptunghi definit prin punctele diagonal opuse de coordonate (x1,y1) şi (x2,y2).

Date de ieşire

În fişierul de ieşire camere.out se vor afla Q numere pe câte un rând, ce reprezintă răspunsurile la întrebări în ordinea în care au fost date în fişierul de intrare.

Restricţii

  • 1 ≤ N,M ≤ 2000
  • 1 ≤ Q ≤ 5000
  • 1 ≤ x1 ≤ x2 ≤ N
  • 1 ≤ y1 ≤ y2 ≤ M
  • Pentru 70 de puncte din cele 130 de puncte se garantează că orice cameră poate fi inclusă complet în orice dreptunghi de query (adică orice cameră se poate translata astfel încât să fie în interiorul dreptunghiului respectiv).

Exemplu

camere.incamere.out
5 6
aabbcc
abbbcc
cbeaed
adeeed
affttz
3
1 1 5 6
2 1 4 5
3 3 5 6
12
8
6

Explicaţie

Avem 3 întrebări

Întrebarea 1 1 5 6 se referă la toată matricea, care are 12 camere.

Dreptunghiul 2 1 4 5 conţine 8 camere, dintre care 4 sunt complete şi alte 4 sunt incomplete.

Dreptunghiul 3 3 5 6 conţine 6 camere, dintre care 5 sunt complete şi o cameră este incompletă.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?