oj.uz

Submission #1040124

# Submission time Handle Problem Language Result Execution time Memory
1040124 2024-07-31T16:43:00 Z hotboy2703 Sweeping (JOI20_sweeping) C++17
100 / 100
 2869 ms 373896 KB 
    #include<bits/stdc++.h>
    using ll = int;
    using namespace std;
    #define pll pair <ll,ll>
    #define fi first
    #define se second
    #define MP make_pair
    #define sz(a) (ll((a).size()))
    #define BIT(mask,i) (((mask) >> (i))&1)
    #define MASK(i) (1LL << (i))
    const ll INF = 1e9;
    const ll MAXN = 1.5e6+100;
    struct query{
        ll t,p,x,y;
    };
    pll ans[MAXN];
    ll val[MAXN*2];
    ll dsu[MAXN*2];
    ll side[MAXN*2];
    vector <ll> comp[MAXN*2];

    ll n,m,q;
    ll join(ll x,ll y){
        if (sz(comp[x]) < sz(comp[y]))swap(x,y);
        for (auto z:comp[y]){comp[x].push_back(z);dsu[z] = x;}
        return x;
    }
    void dnc(ll l,ll r,vector <query> &all){
        ll mid = (l + r) >> 1;
        vector <query> L,R;
        if (sz(all)==0)return;
        for (auto x:all){
            if (x.t == 4){
                dsu[x.p<<1] = x.p<<1;
                dsu[x.p<<1|1] = x.p<<1|1;
                comp[x.p<<1] = {x.p<<1};
                comp[x.p<<1|1] = {x.p<<1|1};
                val[x.p<<1] = x.x;
                val[x.p<<1|1] = x.y;
                side[x.p] = 0;
            }
        }
        if (l==r){
            for (auto [t,p,x,y]:all){
                if (t==1){
                    ans[x] = MP(val[p<<1],val[p<<1|1]);  
                }
            }
            return;
        }
        priority_queue <pll,vector <pll>, greater <> > px,py;
        for (auto cur:all){
            auto [t,p,x,y] = cur;
            if (t==1){
                if (side[p] == 0){
                    // cout<<l<<' '<<r<<' '<<x<<' '<<p<<endl;
                    ans[x] = MP(val[dsu[p<<1]],val[dsu[p<<1|1]]); 
                }
                else if (side[p] == 1)L.push_back(cur);
                else if (side[p] == 2){R.push_back(cur);}
            }
            if (t==2){
                if (n-x>=mid+1){
                    
                    while (!py.empty() && py.top().fi <= x){
                        ll u = py.top().se;
                        py.pop();
                        for (auto z:comp[u]){
                            if (side[z>>1]==0){
                                // cout<<l<<' '<<r<<' '<<(z>>1)<<' '<<val[dsu[16]]<<' '<<val[dsu[17]]<<endl;
                                side[z>>1] = 2;
                                z = z>>1;
                                // if (z==8)cout<<"SUS "<<l<<' '<<r<<' '<<side[z]<<' '<<val[z<<1]<<' '<<val[z<<1|1]<<'\n';
                                R.push_back({4,z,n-x,val[u]});
                            }
                        }
                    }R.push_back(cur);
                    
                }
                else{
                    ll r = 0;
                    while (!px.empty() && px.top().fi <= n-x){
                        ll u = px.top().se;
                        px.pop();
                        // cout<<l<<' '<<r<<' '<<u<<endl;
                        r = r?join(r,u):u;
                    }
                    if (r){
                        val[r] = n-x;
                        // cout<<val[dsu[16]]<<endl;
                        px.push(MP(val[r],r));
                    }
                    L.push_back(cur);
                }
            }
            if (t==3){
                if (x <= mid){
                    
                    while (!px.empty() && px.top().fi <= x){
                        ll u = px.top().se;
                        px.pop();
                        for (auto z:comp[u]){
                            if (side[z>>1]==0){
                                side[z>>1] = 1;
                                // val[z] = val[u];
                                // val[z^1] = n-x;
                                z=z>>1;
                                L.push_back({4,z,val[u],n-x});
                            }
                        }
                    }
                    L.push_back(cur);
                }
                else{
                    
                    ll r = 0;
                    while (!py.empty() && py.top().fi <= n-x){
                        ll u = py.top().se;
                        py.pop();
                        r = r?join(r,u):u;
                    }
                    if (r){
                        val[r] = n-x;
                        py.push(MP(val[r],r));
                    }
                    R.push_back(cur);
                }
            }
            if (t==4){
                if (x >= mid + 1){
                    R.push_back(cur);
                    side[p] = 2;
                }
                else if (y >= n-mid){
                    L.push_back(cur);
                    side[p] = 1;
                }
                else{
                    px.push(MP(val[p<<1],p<<1));
                    py.push(MP(val[p<<1|1],p<<1|1));
                }
            }
        }
        
        dnc(l,mid,L);
        dnc(mid+1,r,R);
    }
    int main(){
        ios_base::sync_with_stdio(0);cin.tie(nullptr);
        // freopen("1.inp","r",stdin);
        // freopen("1.out","w",stdout);
        cin>>n>>m>>q;
        vector <query> all;
        ll ptr = 0;
        for (ll i = 1;i <= m;i ++){
            ll x,y;
            cin>>x>>y;
            all.push_back({4,++ptr,x,y});
        }
        ll cnt=0;
        for (ll i = 1;i <= q;i ++){
            ll t;
            cin>>t;
            if (t==1){
                ll p;
                cin>>p;
                all.push_back({1,p,++cnt,-1});
            }
            if (t==2){
                ll x;
                cin>>x;
                all.push_back({2,-1,x,-1});
            }
            if (t==3){
                ll x;
                cin>>x;
                all.push_back({3,-1,x,-1});
            }
            if (t==4){
                ll x,y;
                cin>>x>>y;
                all.push_back({4,++ptr,x,y});
            }
        }
        dnc(0,n,all);
        for (ll i = 1;i <= cnt;i ++)cout<<ans[i].fi<<' '<<ans[i].se<<'\n';
        return 0;
    }

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 71684 KB Output is correct
2 Correct 18 ms 78996 KB Output is correct
3 Correct 12 ms 78940 KB Output is correct
4 Correct 15 ms 79236 KB Output is correct
5 Correct 17 ms 79196 KB Output is correct
6 Correct 24 ms 71464 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1882 ms 225368 KB Output is correct
2 Correct 1797 ms 234132 KB Output is correct
3 Correct 1781 ms 229068 KB Output is correct
4 Correct 1679 ms 249720 KB Output is correct
5 Correct 2869 ms 246348 KB Output is correct
6 Correct 2523 ms 263552 KB Output is correct
7 Correct 1698 ms 213592 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1340 ms 246244 KB Output is correct
2 Correct 1315 ms 262340 KB Output is correct
3 Correct 1081 ms 246012 KB Output is correct
4 Correct 1372 ms 328548 KB Output is correct
5 Correct 1301 ms 281736 KB Output is correct
6 Correct 1154 ms 244104 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1340 ms 246244 KB Output is correct
2 Correct 1315 ms 262340 KB Output is correct
3 Correct 1081 ms 246012 KB Output is correct
4 Correct 1372 ms 328548 KB Output is correct
5 Correct 1301 ms 281736 KB Output is correct
6 Correct 1154 ms 244104 KB Output is correct
7 Correct 1558 ms 224144 KB Output is correct
8 Correct 1571 ms 233624 KB Output is correct
9 Correct 1584 ms 227724 KB Output is correct
10 Correct 1604 ms 234380 KB Output is correct
11 Correct 1908 ms 282508 KB Output is correct
12 Correct 2300 ms 280516 KB Output is correct
13 Correct 2017 ms 373896 KB Output is correct
14 Correct 91 ms 114712 KB Output is correct
15 Correct 404 ms 187328 KB Output is correct
16 Correct 1563 ms 220432 KB Output is correct
17 Correct 1495 ms 237968 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 71684 KB Output is correct
2 Correct 18 ms 78996 KB Output is correct
3 Correct 12 ms 78940 KB Output is correct
4 Correct 15 ms 79236 KB Output is correct
5 Correct 17 ms 79196 KB Output is correct
6 Correct 24 ms 71464 KB Output is correct
7 Correct 1882 ms 225368 KB Output is correct
8 Correct 1797 ms 234132 KB Output is correct
9 Correct 1781 ms 229068 KB Output is correct
10 Correct 1679 ms 249720 KB Output is correct
11 Correct 2869 ms 246348 KB Output is correct
12 Correct 2523 ms 263552 KB Output is correct
13 Correct 1698 ms 213592 KB Output is correct
14 Correct 1340 ms 246244 KB Output is correct
15 Correct 1315 ms 262340 KB Output is correct
16 Correct 1081 ms 246012 KB Output is correct
17 Correct 1372 ms 328548 KB Output is correct
18 Correct 1301 ms 281736 KB Output is correct
19 Correct 1154 ms 244104 KB Output is correct
20 Correct 1558 ms 224144 KB Output is correct
21 Correct 1571 ms 233624 KB Output is correct
22 Correct 1584 ms 227724 KB Output is correct
23 Correct 1604 ms 234380 KB Output is correct
24 Correct 1908 ms 282508 KB Output is correct
25 Correct 2300 ms 280516 KB Output is correct
26 Correct 2017 ms 373896 KB Output is correct
27 Correct 91 ms 114712 KB Output is correct
28 Correct 404 ms 187328 KB Output is correct
29 Correct 1563 ms 220432 KB Output is correct
30 Correct 1495 ms 237968 KB Output is correct
31 Correct 1689 ms 235632 KB Output is correct
32 Correct 1673 ms 230028 KB Output is correct
33 Correct 1582 ms 204044 KB Output is correct
34 Correct 1943 ms 256284 KB Output is correct
35 Correct 1925 ms 244112 KB Output is correct
36 Correct 1681 ms 247360 KB Output is correct
37 Correct 2553 ms 350672 KB Output is correct
38 Correct 2301 ms 369820 KB Output is correct
39 Correct 2150 ms 330640 KB Output is correct
40 Correct 1660 ms 237196 KB Output is correct