Fișierul intrare/ieșire virus2.in, virus2.out Sursă selectie lot Nerdvana 2022
Autor CodeChef Adăugată de avatar Catalin.Francu 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 stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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, C2N
  • 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).

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii