Cod sursă (job #673972)

#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 char dcnt = 4;
const short di[dcnt] = {-1,  0, +1,  0};
const short dj[dcnt] = { 0, +1,  0, -1};
///                    N   E   S   V

const short MAX_N = 2005;
short 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 short &i, const short &j){
        return (int)(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: char dja;
    private: short nxt_i, nxt_j;
    private: inline void join_around(const short &i, const short &j){
        for(dja=0; dja < dcnt; dja++){
            nxt_i = i + di[dja];
            nxt_j = j + dj[dja];

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

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

    private: inline void dfs(const short &i, const short &j){
        viz[i][j] = true;
        for(char d=0; d < dcnt; d++){
            nxt_i = i + di[d];
            nxt_j = j + dj[d];

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

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

    public: inline void init(){
        for(nxt_i=0; nxt_i<=n+1; nxt_i++) infected[nxt_i][0] = infected[nxt_i][n+1] = true;
        for(nxt_j=0; nxt_j<=n+1; nxt_j++) infected[0][nxt_j] = infected[n+1][nxt_j] = true;
    }

    public: inline void infect(short &i, short &j, short &ii, short &jj){
        for(nxt_i=i; nxt_i<=ii; nxt_i++) infected[nxt_i][j] = infected[nxt_i][jj] = true;
        for(nxt_j=j; nxt_j<=jj; nxt_j++) infected[i][nxt_j] = infected[ii][nxt_j] = true;
    }

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

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


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

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

const string msg[2] = {"NU\n", "DA\n"};
const int MAX_Q = 100005;
int qcnt;
struct query{
    short type, i, j, 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;
}