oj.uz

Submission #1040105

# Submission time Handle Problem Language Result Execution time Memory
1040105 2024-07-31T16:20:40 Z hotboy2703 Sweeping (JOI20_sweeping) C++17
100 / 100
 3394 ms 931560 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 29 ms 72792 KB Output is correct
2 Correct 42 ms 72156 KB Output is correct
3 Correct 26 ms 72148 KB Output is correct
4 Correct 41 ms 72920 KB Output is correct
5 Correct 28 ms 72928 KB Output is correct
6 Correct 34 ms 72088 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2458 ms 430392 KB Output is correct
2 Correct 2252 ms 430892 KB Output is correct
3 Correct 2353 ms 425192 KB Output is correct
4 Correct 2113 ms 548660 KB Output is correct
5 Correct 3290 ms 473948 KB Output is correct
6 Correct 2924 ms 518032 KB Output is correct
7 Correct 2294 ms 409952 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1961 ms 497012 KB Output is correct
2 Correct 1928 ms 524488 KB Output is correct
3 Correct 1606 ms 525792 KB Output is correct
4 Correct 2082 ms 777312 KB Output is correct
5 Correct 2036 ms 641512 KB Output is correct
6 Correct 1739 ms 494044 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1961 ms 497012 KB Output is correct
2 Correct 1928 ms 524488 KB Output is correct
3 Correct 1606 ms 525792 KB Output is correct
4 Correct 2082 ms 777312 KB Output is correct
5 Correct 2036 ms 641512 KB Output is correct
6 Correct 1739 ms 494044 KB Output is correct
7 Correct 2404 ms 437016 KB Output is correct
8 Correct 2441 ms 467844 KB Output is correct
9 Correct 2381 ms 443492 KB Output is correct
10 Correct 2327 ms 504116 KB Output is correct
11 Correct 2742 ms 649796 KB Output is correct
12 Correct 3275 ms 580440 KB Output is correct
13 Correct 2931 ms 898028 KB Output is correct
14 Correct 150 ms 188300 KB Output is correct
15 Correct 560 ms 313180 KB Output is correct
16 Correct 2365 ms 435224 KB Output is correct
17 Correct 2418 ms 470584 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 72792 KB Output is correct
2 Correct 42 ms 72156 KB Output is correct
3 Correct 26 ms 72148 KB Output is correct
4 Correct 41 ms 72920 KB Output is correct
5 Correct 28 ms 72928 KB Output is correct
6 Correct 34 ms 72088 KB Output is correct
7 Correct 2458 ms 430392 KB Output is correct
8 Correct 2252 ms 430892 KB Output is correct
9 Correct 2353 ms 425192 KB Output is correct
10 Correct 2113 ms 548660 KB Output is correct
11 Correct 3290 ms 473948 KB Output is correct
12 Correct 2924 ms 518032 KB Output is correct
13 Correct 2294 ms 409952 KB Output is correct
14 Correct 1961 ms 497012 KB Output is correct
15 Correct 1928 ms 524488 KB Output is correct
16 Correct 1606 ms 525792 KB Output is correct
17 Correct 2082 ms 777312 KB Output is correct
18 Correct 2036 ms 641512 KB Output is correct
19 Correct 1739 ms 494044 KB Output is correct
20 Correct 2404 ms 437016 KB Output is correct
21 Correct 2441 ms 467844 KB Output is correct
22 Correct 2381 ms 443492 KB Output is correct
23 Correct 2327 ms 504116 KB Output is correct
24 Correct 2742 ms 649796 KB Output is correct
25 Correct 3275 ms 580440 KB Output is correct
26 Correct 2931 ms 898028 KB Output is correct
27 Correct 150 ms 188300 KB Output is correct
28 Correct 560 ms 313180 KB Output is correct
29 Correct 2365 ms 435224 KB Output is correct
30 Correct 2418 ms 470584 KB Output is correct
31 Correct 2150 ms 506400 KB Output is correct
32 Correct 2482 ms 427252 KB Output is correct
33 Correct 2262 ms 385628 KB Output is correct
34 Correct 2766 ms 497392 KB Output is correct
35 Correct 2787 ms 462004 KB Output is correct
36 Correct 2248 ms 516804 KB Output is correct
37 Correct 3394 ms 841316 KB Output is correct
38 Correct 3277 ms 931560 KB Output is correct
39 Correct 3355 ms 798848 KB Output is correct
40 Correct 2389 ms 471596 KB Output is correct