oj.uz

Submission #1040123

# Submission time Handle Problem Language Result Execution time Memory
1040123 2024-07-31T16:42:01 Z hotboy2703 Sweeping (JOI20_sweeping) C++17
100 / 100
 3078 ms 625488 KB 
#include<bits/stdc++.h>
using ll = long long;
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 = 1e18;
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 27 ms 72280 KB Output is correct
2 Correct 15 ms 79260 KB Output is correct
3 Correct 19 ms 71904 KB Output is correct
4 Correct 24 ms 72324 KB Output is correct
5 Correct 25 ms 72396 KB Output is correct
6 Correct 14 ms 79260 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2032 ms 329556 KB Output is correct
2 Correct 2033 ms 328584 KB Output is correct
3 Correct 2003 ms 329976 KB Output is correct
4 Correct 1948 ms 392556 KB Output is correct
5 Correct 2978 ms 365084 KB Output is correct
6 Correct 2628 ms 391380 KB Output is correct
7 Correct 1978 ms 313268 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1552 ms 375588 KB Output is correct
2 Correct 1521 ms 401068 KB Output is correct
3 Correct 1274 ms 376388 KB Output is correct
4 Correct 1734 ms 538760 KB Output is correct
5 Correct 1582 ms 451452 KB Output is correct
6 Correct 1382 ms 359100 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1552 ms 375588 KB Output is correct
2 Correct 1521 ms 401068 KB Output is correct
3 Correct 1274 ms 376388 KB Output is correct
4 Correct 1734 ms 538760 KB Output is correct
5 Correct 1582 ms 451452 KB Output is correct
6 Correct 1382 ms 359100 KB Output is correct
7 Correct 1919 ms 320316 KB Output is correct
8 Correct 1889 ms 343312 KB Output is correct
9 Correct 1926 ms 332004 KB Output is correct
10 Correct 1861 ms 341932 KB Output is correct
11 Correct 2299 ms 446508 KB Output is correct
12 Correct 2714 ms 438832 KB Output is correct
13 Correct 2494 ms 623816 KB Output is correct
14 Correct 113 ms 156816 KB Output is correct
15 Correct 518 ms 249700 KB Output is correct
16 Correct 1875 ms 316548 KB Output is correct
17 Correct 1843 ms 351660 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 72280 KB Output is correct
2 Correct 15 ms 79260 KB Output is correct
3 Correct 19 ms 71904 KB Output is correct
4 Correct 24 ms 72324 KB Output is correct
5 Correct 25 ms 72396 KB Output is correct
6 Correct 14 ms 79260 KB Output is correct
7 Correct 2032 ms 329556 KB Output is correct
8 Correct 2033 ms 328584 KB Output is correct
9 Correct 2003 ms 329976 KB Output is correct
10 Correct 1948 ms 392556 KB Output is correct
11 Correct 2978 ms 365084 KB Output is correct
12 Correct 2628 ms 391380 KB Output is correct
13 Correct 1978 ms 313268 KB Output is correct
14 Correct 1552 ms 375588 KB Output is correct
15 Correct 1521 ms 401068 KB Output is correct
16 Correct 1274 ms 376388 KB Output is correct
17 Correct 1734 ms 538760 KB Output is correct
18 Correct 1582 ms 451452 KB Output is correct
19 Correct 1382 ms 359100 KB Output is correct
20 Correct 1919 ms 320316 KB Output is correct
21 Correct 1889 ms 343312 KB Output is correct
22 Correct 1926 ms 332004 KB Output is correct
23 Correct 1861 ms 341932 KB Output is correct
24 Correct 2299 ms 446508 KB Output is correct
25 Correct 2714 ms 438832 KB Output is correct
26 Correct 2494 ms 623816 KB Output is correct
27 Correct 113 ms 156816 KB Output is correct
28 Correct 518 ms 249700 KB Output is correct
29 Correct 1875 ms 316548 KB Output is correct
30 Correct 1843 ms 351660 KB Output is correct
31 Correct 1853 ms 361968 KB Output is correct
32 Correct 2064 ms 331700 KB Output is correct
33 Correct 1828 ms 297744 KB Output is correct
34 Correct 2413 ms 377360 KB Output is correct
35 Correct 2503 ms 353064 KB Output is correct
36 Correct 2189 ms 368440 KB Output is correct
37 Correct 3078 ms 599464 KB Output is correct
38 Correct 3042 ms 625488 KB Output is correct
39 Correct 3009 ms 549688 KB Output is correct
40 Correct 2088 ms 349420 KB Output is correct