Submission #1084948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084948		phong	Sweeping (JOI20_sweeping)	C++17	100 / 100	3984 ms	640828 KiB

sweeping

#include<bits/stdc++.h>
#define ll long long
const int nmax = 1e6 + 5, N = 1e6;
const ll oo = 1e18 + 5, base = 311;
const int lg = 62, tx = 26;
const ll mod = 1e9 + 7;
#define pii pair<ll, ll>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

struct DSU{
    int r[nmax], vis[nmax], dx[nmax];
    vector<int> tmp, adj[nmax];
    int get(int u){
        tmp.push_back(u);
        return r[u] ? r[u] = get(r[u]) : u;
    }
    void init(){
        for(int i= 1; i <= N; ++i) adj[i].push_back(i);
    }
    void Union(int u, int v){
        u = get(u);v = get(v);
        if(u != v){
            if(adj[u].size() > adj[v].size()) swap(u, v);
            for(auto p : adj[u]) adj[v].push_back(p);
            adj[u].clear();
            r[u] = v;
        }
    }
    void clear(){
        for(auto p : tmp){
            adj[p].clear();
            adj[p].push_back(p);
            dx[p] = 0;
            r[p] = 0;
            vis[p] = 0;
        }
//        for(int i = 1; i <= 1e5; ++i) vis[i]= 0;
        tmp.clear();
    }
}A, B;
pii a[nmax], ans[nmax];
struct node{
    int id, x, y, idx;
};
bool inside(int l, int r,int h, int w, int x, int y){
    return l <= y && y <= l + h && x <= r + w && r <= x;
}
int vis[nmax];
int scd = 0;
/*
4 3 2
4 0
1 2
3 0
3 3
1 3
*/
vector<int> lol;
void add(int u, int id){
    vis[u] = id;
    lol.push_back(u);
}
void Del(){
    for(auto p : lol) vis[p] = 0;
    lol.clear();
}
pii dx[5];
void solve(int l, int r, int N, vector<node> Q){
    bool ok = 0;
    for(auto p : Q) ok |= (p.id == 1);
    if(!ok) return;
    int k = N / 2;
    int h = N - k, w = k;
    vector<node> Ql, Qr;
    priority_queue<pii, vector<pii>, greater<pii>> xs, ys;
    int xl, yl, xr, yr;
    yl = l + h, xl = r;
    yr = l, xr = r + w;
    if(N == 1){
        vector<int> AA, BB, CC;
        dx[0] = {r, l};
        dx[1] = {r + 1, l};
        dx[2] = {r, l + 1};
        Del();
        for(auto [t, x, y, id] : Q){
            if(t == 1){
                int val = vis[x];
                ans[id] = dx[val];
            }
            else if(t == 2){
                if(x == 0){
                    while(BB.size()){
                        int it = BB.back();
                        CC.push_back(it);
                        BB.pop_back();
                        add(it, 1);
                    }
                }
            }
            else if(t == 3){
                int L = 1 - x;
                if(L == 1){
                    while(BB.size()){
                        int it = BB.back();
                        AA.push_back(it);
                        BB.pop_back();
                        add(it, 2);
                    }
                }
            }
            else if(t == 4){
                pii tx = {x, y};
//                cout << tx.fi << ' ' << tx.se << ' ' << id << endl;
                if(tx == dx[0]) BB.push_back(id), add(id, 0);
                else if(tx == dx[1]) CC.push_back(id), add(id, 1);
                else AA.push_back(id), add(id, 2);
            }
        }

        return;
    }
//    cout<<endl;
    vector<int> one;
    Del();
    for(auto [t, x, y, id] : Q){
        if(t == 1){
            if(vis[x] == 0){
                int u = A.get(x);
                int v = B.get(x);
                ans[id] = {A.dx[u], B.dx[v]};
            }
            else{
                if(vis[x] == 1){
                    Ql.push_back({t, x, y, id});
                }
                else{
                    Qr.push_back({t, x, y, id});
                }
            }
        }
        else if(t == 2){
            int L = x;
            if(L >= h){
                while(xs.size()){
                    pii tmp = xs.top();
                    if(tmp.fi <= r + N - L){
                        one.push_back(tmp.se);
                        xs.pop();
                    }
                    else{
                        break;
                    }
                }
                Ql.push_back({t, L - h, 0, id});
                if(one.empty()) continue;
                for(int i = 1; i < one.size(); ++i) A.Union(one[i - 1], one[i]);
                int root = A.get(one[0]);
                A.dx[root] = r + N - L;
                xs.push({r + N - L, root});
                one.clear();
            }
            else{
                while(ys.size()){
                    pii tmp = ys.top();
                    if(tmp.fi <= l + L){
                        int root = tmp.se;
                        for(auto v : B.adj[root]){
                            if(B.vis[v] == 1 || A.vis[v] == 1) continue;
                            Qr.push_back({4, r + w, tmp.fi, v});
                            B.vis[v] = 1;
                            B.tmp.push_back(v);
                            add(v, 2);
                        }
                        ys.pop();
                    }
                    else break;
                }
                Qr.push_back({t, L, 0, id});
            }
        }
        else if(t == 3){
            int L = N - x;
            if(L > h){

                while(xs.size()){
                    pii tmp = xs.top();
                    if(tmp.fi <= r + N - L){
                        int root = tmp.se;
                        for(auto v : A.adj[root]){
                            if(B.vis[v] == 1 || A.vis[v] == 1) continue;
                            Ql.push_back({4, tmp.fi, l + h, v});
                            A.vis[v] = 1;
                            A.tmp.push_back(v);
                            add(v, 1);
                        }
                        xs.pop();
                    }
                    else break;
                }
                Ql.push_back({t, x, 0, id});
            }
            else{
                while(ys.size()){
                    pii tmp = ys.top();
                    if(tmp.fi <= l + L){
                        one.push_back(tmp.se);
                        ys.pop();
                    }
                    else break;
                }
                Qr.push_back({t, x - w, 0, id});
                if(one.empty()) continue;
                for(int i = 1; i < one.size(); ++i) B.Union(one[i - 1], one[i]);
                int root = B.get(one[0]);
                B.dx[root] = l + L;
                ys.push({l + L, root});
                one.clear();
            }
        }
        else{
            if(inside(l, r, h, w, x, y)){
                xs.push({x, id});
                ys.push({y, id});
                A.dx[id] = x;
                B.dx[id] = y;
            }
            else{
                if(inside(yl, xl, k, k, x, y)){
                    Ql.push_back({t, x, y, id});
                    add(id, 1);
                }
                else{
                    Qr.push_back({t, x, y, id});
                    add(id, 2);
                }
            }
        }
    }
    A.clear();B.clear();
    if(N == 1) return;
    solve(yl, xl, N - h, Ql);
    solve(yr, xr, N - w, Qr);
}
int n, m, q;
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> m >> q;
    vector<node> Q;
    for(int i = 1, x, y; i <= m; ++i){
        cin >> x >> y;
        Q.push_back({4, x, y, i});
        a[i] = {x, y};
    }
    A.init(), B.init();
    int scc = m;vector<int> tmp;
    for(int e = 1; e <= q; ++e){
        int t, p, x, y;
        cin >> t;
        if(t != 4){
            cin >> p;
            Q.push_back({t, p, 0, e});
            if(t == 1)tmp.push_back(e);
        }
        else{
            cin >> x >> y;
            Q.push_back({4, x, y, ++scc});
            a[scc] = {x, y};
        }
    }
    solve(0, 0, n, Q);
    for(auto p : tmp) cout << ans[p].fi << ' ' << ans[p].se << endl;
}
/*
4 3 2
4 0
1 2
3 0
3 3
1 3


*/

Compilation message (stderr)

sweeping.cpp: In function 'void solve(int, int, int, std::vector<node>)':
sweeping.cpp:159:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |                 for(int i = 1; i < one.size(); ++i) A.Union(one[i - 1], one[i]);
      |                                ~~^~~~~~~~~~~~
sweeping.cpp:8:12: warning: narrowing conversion of 'tmp.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
    8 | #define fi first
      |            ^
sweeping.cpp:172:57: note: in expansion of macro 'fi'
  172 |                             Qr.push_back({4, r + w, tmp.fi, v});
      |                                                         ^~
sweeping.cpp:8:12: warning: narrowing conversion of 'tmp.std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
    8 | #define fi first
      |            ^
sweeping.cpp:194:50: note: in expansion of macro 'fi'
  194 |                             Ql.push_back({4, tmp.fi, l + h, v});
      |                                                  ^~
sweeping.cpp:216:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  216 |                 for(int i = 1; i < one.size(); ++i) B.Union(one[i - 1], one[i]);
      |                                ~~^~~~~~~~~~~~
sweeping.cpp: At global scope:
sweeping.cpp:248:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  248 | main(){
      | ^~~~

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