Submission #781965

#	Time	Username	Problem	Language	Result	Execution time	Memory
781965		doowey	Sweeping (JOI20_sweeping)	C++17	100 / 100	3233 ms	413536 KiB

sweeping

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int M = (int)1e6 + 10;
int sol[M][2];

int n;

int val[2 * M];
int par[2 * M];
vector<int> lis[2 * M];
int c;

int id_x[M];
int id_y[M];
int away[M];

int fin(int u){
    if(par[u] == u) return u;
    return par[u]=fin(par[u]);
}

int get_val(int u){
    return val[fin(u)];
}

void unite(int x, int y){
    x=fin(x);
    y=fin(y);
    if(x==y) return;
    par[x]=y;
    val[y]=max(val[y],val[x]);
    if(lis[x].size() > lis[y].size()) swap(lis[x], lis[y]);
    for(auto p : lis[x]) lis[y].push_back(p);
    lis[x].clear();
}

bool yessir(int node){
    return par[node] == node;
}

void solve(int x, int y, vector<array<int, 3>> qr){
    if(qr.empty()) return;
    int sz = (n - x - y);
    if(sz == 0){
        for(auto p : qr){
            if(p[0] >= 1){
                id_x[p[0]] = p[1];
                id_y[p[0]] = p[2];
            }
            else if(p[0] == -1){
                sol[p[2]][0] = id_x[p[1]];
                sol[p[2]][1] = id_y[p[1]];
            }
        }
        return;
    }
    c = 0;
    int X = x + (sz + 1) / 2;
    int Y = y + sz / 2 + 1;
    vector<array<int, 3>> rig, up;
    priority_queue<pii, vector<pii>, greater<pii>> xc; // {x, comp}
    priority_queue<pii, vector<pii>, greater<pii>> yc; // {y, comp}

    int nw;
    int L;
    for(auto p : qr){
        if(p[0] >= 1){
            if(p[1] >= X){
                rig.push_back(p);
                away[p[0]] = 0;
                continue;
            }
            if(p[2] >= Y){
                up.push_back(p);
                away[p[0]] = 1;
                continue;
            }
            away[p[0]]=-1;
            id_x[p[0]] = c;
            val[c] = p[1];
            par[c] = c;
            lis[c].clear();
            lis[c].push_back(p[0]);
            xc.push(mp(val[c], c));
            c ++ ;
            id_y[p[0]] = c;
            val[c] = p[2];
            par[c] = c;
            lis[c].clear();
            lis[c].push_back(p[0]);
            yc.push(mp(val[c], c));
            c ++ ;
        }
        else if(p[0] == -1){
            if(away[p[1]] == 0) {
                rig.push_back(p);
            }
            else if(away[p[1]] == 1){
                up.push_back(p);
            }
            else if(get_val(id_x[p[1]]) >= X){
                rig.push_back(p);
            }
            else if(get_val(id_y[p[1]]) >= Y){
                up.push_back(p);
            }
            else{
                sol[p[2]][0] = get_val(id_x[p[1]]);
                sol[p[2]][1] = get_val(id_y[p[1]]);
            }
        }
        else if(p[0] == -2){
            L = p[1];
            if(L >= Y){
                int nw = c;
                lis[c].clear();
                par[c] = c;
                val[c] = n - L;
                c ++ ;
                while(!xc.empty() && xc.top().fi < n - L){
                    unite(xc.top().se, nw);
                    xc.pop();
                }
                xc.push(mp(val[nw], nw));
                up.push_back(p);
            }
            else{
                rig.push_back(p);
                while(!yc.empty() && yc.top().fi <= L){
                    for(auto v : lis[yc.top().se]){
                        if(away[v] != -1) continue;
                        rig.push_back({v, n - L, yc.top().fi});
                        away[v]=0;
                    }
                    yc.pop();
                }
            }
        }
        else{ // p[0] == -3
            L = p[1];
            if(L >= X){
                int nw = c;
                lis[c].clear();
                par[c] = c;
                val[c] = n - L;
                c ++ ;
                while(!yc.empty() && yc.top().fi < n - L){
                    unite(yc.top().se, nw);
                    yc.pop();
                }
                yc.push(mp(val[nw], nw));
                rig.push_back(p);
            }
            else{
                up.push_back(p);
                while(!xc.empty() && xc.top().fi <= L){
                    for(auto v : lis[xc.top().se]){
                        if(away[v] != -1) continue;
                        up.push_back({v, xc.top().fi, n - L});
                        away[v]=1;
                    }
                    xc.pop();
                }
            }
        }
    }
    solve(x, Y, up);
    solve(X, y, rig);
}

int main(){
    //fastIO;
    int m, q;
    cin >> n >> m >> q;
    vector<array<int, 3>> query;
    int x, y;
    int c = 1;
    for(int i = 1; i <= m; i ++ ){
        cin >> x >> y;
        query.push_back({c, x, y});
        c ++ ;
    }
    int typ;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> typ;
        sol[iq][0] = sol[iq][1] = -1;
        if(typ <= 3){
            cin >> x;
            query.push_back({-typ,x,iq});
        }
        else{
            cin >> x >> y;
            query.push_back({c, x, y});
            c ++ ;
        }
    }
    solve(0, 0, query);
    for(int iq = 1; iq <= q; iq ++ ){
        if(sol[iq][0] == -1) continue;
        cout << sol[iq][0] << " " << sol[iq][1] << "\n";
    }
    return 0;
}

Compilation message (stderr)

sweeping.cpp: In function 'void solve(int, int, std::vector<std::array<int, 3> >)':
sweeping.cpp:74:9: warning: unused variable 'nw' [-Wunused-variable]
   74 |     int nw;
      |         ^~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25