Cod sursă (job #730486)

#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2000;
const int QMAX = 1e5;

ifstream fin( "virus2.in" );
ofstream fout( "virus2.out" );

struct Query{
  int tip;
  int l1, l2, c1, c2;
  string ans;
};
Query query[QMAX+1];

int n;
int comp = 1;
int mat[NMAX+2][NMAX+2];

void set_border( int lin1, int lin2, int col1, int col2 ) {
  int i;
  for( i = lin1; i <= lin2; i++ )
    mat[i][col1] = mat[i][col2] = comp;
  for( i = col1; i <= col2; i++ )
    mat[lin1][i] = mat[lin2][i] = comp;
  comp++;
}

int parent[NMAX*NMAX+1];

int findd( int x ) {
  if( x == parent[x] )
    return x;
  return parent[x] = findd( parent[x] );
}

void unite( int a, int b ) {
  int x = findd( a );
  int y = findd( b );
  if( x != y )
    parent[x] = y;
}

int dlin[4] = { -1, 1, 0, 0 };
int dcol[4] = { 0, 0, -1, 1 };

void fil( int lin, int col, int nr ) {
  queue<pair<int, int>> q;
  q.push( { lin, col } );
  mat[lin][col] = nr;
  while( !q.empty() ) {
    int lin = q.front().first;
    int col = q.front().second;
    q.pop();
    for( int k = 0; k < 4; k++ ) {
      if( lin + dlin[k] >= 1 && lin + dlin[k] <= n && col + dcol[k] >= 1 && col + dcol[k] <= n && !mat[lin+dlin[k]][col+dcol[k]] ) {
        mat[lin+dlin[k]][col+dcol[k]] = nr;
        q.push( { lin + dlin[k], col + dcol[k] } );
      }
    }
  }
}

void desinfect( int lin, int col ) {
  int k;
  for( k = 0; k < 4; k++ ) {
    if( mat[lin][col] < mat[lin+dlin[k]][col+dcol[k]] )
      unite( mat[lin][col], mat[lin+dlin[k]][col+dcol[k]] );
  }
}

int main() {
  int q, i, j, last;
  fin >> n >> q;
  for( i = 0; i < q; i++ ) {
    fin >> query[i].tip >> query[i].l1 >> query[i].c1 >> query[i].l2 >> query[i].c2;
    if( query[i].tip == 1 )
      set_border( query[i].l1, query[i].l2, query[i].c1, query[i].c2 );
  }
  last = comp - 1;
  for( i = 1; i <= n; i++ ) {
    for( j = 1; j <= n; j++ ) {
      if( !mat[i][j] ) {
        fil( i, j, comp );
        comp++;
      }
    }
  }
  for( i = 1; i <= n * n; i++ )
    parent[i] = i;
  for( i = q - 1; i >= 0; i-- ) {
    if( query[i].tip == 2 ) {
      if( mat[query[i].l1][query[i].c1] > last && mat[query[i].l2][query[i].c2] > last ) {
        int x = findd( mat[query[i].l1][query[i].c1] );
        int y = findd( mat[query[i].l2][query[i].c2] );
        if( x == y )
          query[i].ans = "DA";
        else query[i].ans = "NU";
      }
      else
        query[i].ans = "NU";
    }
    else {
      last--;
      for( j = query[i].l1; j <= query[i].l2; j++ ) {
        desinfect( j, query[i].c1 );
        desinfect( j, query[i].c2 );
      }
      for( j = query[i].c1; j <= query[i].c2; j++ ) {
        desinfect( query[i].l1, j );
        desinfect( query[i].l2, j );
      }
    }
  }
  for( i = 0; i < q; i++ ) {
    if( query[i].tip == 2 )
      fout << query[i].ans << "\n";
  }
  return 0;
}