| Fișierul intrare/ieșire | virus2.in, virus2.out | Sursă | selectie lot Nerdvana 2022 |
|---|---|---|---|
| Autor | CodeChef | Adăugată de |
Cătălin Frâncu
•
Catalin.Francu
|
| Timp de execuție pe test | 1.5 sec | Limită de memorie | 262144 KB |
| Scorul tău | N/A | Dificultate |
  3
|
Poți vedea testele pentru această problemă accesând
atașamentele
.
Vezi soluțiile trimise | Statistici
Virus2
Această problemă provine de pe CodeChef (am creat teste noi).
O rețea de calculatoare este formată din N2 calculatoare așezate într-un pătrat cu N linii și N coloane. Inițial toate calculatoarele sînt pornite. Fiecare calculator este conectat prin cabluri la vecinii săi din cele patru direcții, iar oricare două calculatoare pot comunica dacă între ele există o cale formată din calculatoare pornite și conectate prin cabluri. Un virus straniu începe să infecteze această rețea. Fiecare pas al infecției oprește calculatoarele aflate pe un dreptunghi (nu și pe cele din interiorul dreptunghiului). Dreptunghiurile de la oricare doi pași nu se intersectează și nu coincid, dar pot fi incluse unul într-altul.
Administratorul de sistem dorește să știe, pe parcursul infecției, dacă diverse perechi de calculatoare mai pot comunica. Concret, se dau Q operații de două tipuri posibile, în ordine cronologică:
- 1 L1 C1 L2 C2: virusul oprește calculatoarele de pe dreptunghiul -(L2, C2).
- 2 L1 C1 L2 C2: administratorul se întreabă dacă cele două calculatoare de la (L1, C1) și (L2, C2) sînt pornite și pot comunica între ele.
Se cere să afișați răspunsurile la toate operațiile de tipul 2.
Date de intrare
Fișierul de intrare virus2.in conține pe prima linie întregii N și Q, separați prin spații. Fiecare dintre următoarele Q linii conține cinci întregi T, L1, C1, L2 și C2 care codifică o operație.
Date de ieșire
În fișierul de ieșire virus2.out afișați, pentru fiecare operație de tip 2, în aceeași ordine ca la intrare, cîte o linie cu textul DA dacă cele două calculatoare sînt pornite și pot comunica sau NU în caz contrar.
Restricții
- 3 ≤ N ≤ 2.000
- 1 ≤ Q ≤ 100.000
- 1 ≤ L1, L2, C1, C2 ≤ N
- Pentru operațiile de tip 1, L1 < L2 și C1 < C2.
- Pentru operațiile de tip 2, (L1, C1) și (L2, C2) sînt distincte.
| puncte | restricții | |
|---|---|---|
| 1 | 30 | N ≤ 100, Q ≤ 1.000 |
| 2 | 70 | Fără restricții suplimentare. |
Exemplu
| virus2.in | virus2.out | configurație finală |
|---|---|---|
| 10 8 2 3 6 8 2 1 2 2 8 7 2 5 5 4 3 2 5 5 4 1 1 4 4 6 6 2 5 5 4 3 1 2 8 6 10 2 6 9 7 9 |
DA DA NU NU NU |
* * * * * * * * * * * · · · · · · · · · * · * * * * · · * · * · * · · · · · * · * · * · * · · · * · * · * · · · · · · · * · * * * * · * * * * · · · · · · * * * * * * * * * * * * * * * * * * * * * * * |
Explicație
Inițial toate calculatoarele sînt pornite, deci (3,6) și (8,2) pot comunica. După oprirea dreptunghiului (2,2)-(8,7), calculatoarele (5,5) și (4,3) se află în interiorul dreptunghiului și pot comunica, dar (5,5) și (4,1) sînt separate de dreptunghi și nu pot comunica. După oprirea dreptunghiului (4,4)-(6,6), calculatoarele (5,5) și (4,3) nu mai pot comunica. După oprirea dreptunghiului (2,8)-(6,10), calculatorul (6,9) este oprit, deci implicit nu poate comunica cu (7,9). Configurația finală este descrisă pe ultima coloană (calculatoarele pornite sînt marcate cu *, cele oprite cu punct).
