Cod sursă (job #673966)

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target ("avx2,popcnt")

using namespace std;

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

const int dcnt = 4;
const int di[dcnt] = {-1,  0, +1,  0};
const int dj[dcnt] = { 0, +1,  0, -1};
///                    N   E   S   V

const int MAX_N = 2005;
int n;
struct DSU{
    private: bitset <MAX_N> infected[MAX_N], viz[MAX_N];
    private: int parent[MAX_N * MAX_N];

    private: inline int node(const int &i, const int &j){
        return (i-1) * n + j;
    }

    private: int root, aux;
    private: inline int get_root(int nod){
        root = nod;
        while(parent[root] != 0)
            root = parent[root];

        while(parent[nod] != 0){
            aux = nod;
            nod = parent[nod];
            parent[aux] = root;
        }

        return root;
    }

    private: int ru, rv;
    private: inline void join(const int &u, const int &v){
        ru = get_root(u);
        rv = get_root(v);
        if(ru != rv)
            parent[ru] = rv;
    }

    private: int nxt_i, nxt_j;
    private: inline void join_around(const int &i, const int &j){
        for(int d=0; d < dcnt; d++){
            nxt_i = i + di[d];
            nxt_j = j + dj[d];

            if(!infected[nxt_i][nxt_j])
                join(node(nxt_i, nxt_j), node(i, j));
        }
    }

    public: inline bool query(const int &i, const int &j, const int &ii, const int &jj){
        return get_root(node(i, j)) == get_root(node(ii, jj));
    }

    private: inline void dfs(const int &i, const int &j){
        viz[i][j] = true;
        for(int ii, jj, d=0; d < dcnt; d++){
            ii = i + di[d];
            jj = j + dj[d];

            if(!infected[ii][jj] && !viz[ii][jj]){
                join(node(ii, jj), node(i, j));
                dfs(ii, jj);
            }
        }
    }

    public: inline void build(){
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(!infected[i][j] && !viz[i][j])
                    dfs(i, j);
    }

    public: inline void init(){
        infect(0, 0, n+1, 0);
        infect(0, 0, 0, n+1);
        infect(n+1, 0, n+1, n+1);
        infect(0, n+1, n+1, n+1);
    }

    public: inline void infect(int i, int j, int ii, int jj){
        for(int r=i; r<=ii; r++) infected[r][j] = infected[r][jj] = true;
        for(int c=j; c<=jj; c++) infected[i][c] = infected[ii][c] = true;
    }

    public: inline void disinfect(int i, int j, int ii, int jj){
        for(int r=i; r<=ii; r++){
            infected[r][j] = false;
            join(node(r, j), node(i, j));
            join_around(r, j);

            infected[r][jj] = false;
            join(node(r, jj), node(i, j));
            join_around(r, jj);
        }


        for(int c=j; c<=jj; c++){
            infected[i][c] = false;
            join(node(i, c), node(i, j));
            join_around(i, c);

            infected[ii][c] = false;
            join(node(ii, c), node(i, j));
            join_around(ii, c);
        }
    }
} dsu;

const string msg[2] = {"NU\n", "DA\n"};
const int MAX_Q = 100005;
int qcnt;
struct query{
    int type;
    int i, j;
    int ii, jj;
} q[MAX_Q];
stack <string> answer;

int main (){
    ios_base::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);

    fin>>n>>qcnt;

    dsu.init();
    for(int i=1; i<=qcnt; i++){
        fin>>q[i].type>>q[i].i>>q[i].j>>q[i].ii>>q[i].jj;
        if(q[i].type == 1) ///update
            dsu.infect(q[i].i, q[i].j, q[i].ii, q[i].jj);
    }

    dsu.build();
    for(int i=qcnt; i>=1; i--){
        if(q[i].type == 1) ///update
            dsu.disinfect(q[i].i, q[i].j, q[i].ii, q[i].jj);
        else ///query
            answer.push(msg[dsu.query(q[i].i, q[i].j, q[i].ii, q[i].jj)]);
    }

    while(!answer.empty()){
        fout<<answer.top();
        answer.pop();
    }
    return 0;
}