Pracsiu Dan (dnprx) Se dă o matrice cu 2 linii si n coloane care are k celule ocupate. Se dau q interogări de forma (x1, y1, x2, y2), cu următoarea semnificație: dacă se ocupă două celule libere distincte ale matricii inițiale, (x1, y1) și (x2, y2), se poate pava complet matricea cu piese de domino de dimensiuni 2 x 1 și 1 x 2? După efectuarea unei interogări celulele ocupate asociate acesteia vor deveni din nou libere (modificările aduse matricei nu persistă între interogări).
Cerința
Să se determine, pentru fiecare interogare, dacă este posibil ca matricea să fie pavată complet cu piese de domino de dimensiuni 2 x 1 și 1 x 2.
Date de intrare
Pe prima linie a fișierului dominoes.in se află n și k. Pe următoarele k linii se află coordonatele pozițiilor ocupate, de forma (x, y). Pe a (k + 2)-a linie se află q. Pe fiecare dintre următoarele q linii se găsesc valorile x1, y1, x2 și y2, separate prin câte un spațiu, cu semnificația din cerință.
Date de ieșire
Fișierul de ieșire dominoes.out va conține q linii, pe fiecare linie aflându-se răspunsul (1 dacă se poate, respectiv 0 dacă nu se poate) corespunzător câte unei interogări, în ordinea în care acestea se găsesc în fișierul de intrare.
Restricții și precizări
- Se garantează faptul că matricea inițială se poate pava complet cu piese de domino.
1 ≤ x, x1, x2 ≤ 21 ≤ y, y1, y2 ≤ n0 ≤ k ≤ 100.000,kpar1 ≤ q ≤ 100.0001 ≤ n ≤ 1.000.000.000- Pentru 9 puncte,
n, k, q ≤ 8 - Pentru 6 puncte,
k = 0 - Pentru 11 puncte,
n, k, q ≤ 5000 - Pentru 12 puncte,
k, q ≤ 5000 - Pentru 23 de puncte,
n ≤ 100.000 - Pentru 6 puncte,
y1 = y2pentru fiecare interogare - Pentru 8 puncte,
y1 ≠ y2pentru fiecare interogare - Pentru 25 de puncte, fără alte restricții suplimentare
Exemplul 1:
dominoes.in
5 2 1 1 2 5 4 1 3 2 3 2 1 1 5 2 3 2 4 1 2 2 4
dominoes.out
0 1 1 1
Explicație
Dedesubt se găsesc configurațiile matricei pentru fiecare interogare, in ordinea din input, cu negru fiind marcate celulele blocate:
Exemplul 2:
dominoes.in
6 4 1 1 2 3 1 4 2 6 3 1 2 2 2 1 2 1 3 1 2 1 5
dominoes.out
0 1 0
Explicație
Configurațiile matricei pentru fiecare interogare:
Exemplul 3:
dominoes.in
6 2 1 1 2 3 3 1 4 2 6 1 4 2 5 1 3 2 5
dominoes.out
1 0 0
Explicație
Configurațiile matricei pentru fiecare interogare:
