oj.uz

Submission #1018680

# Submission time Handle Problem Language Result Execution time Memory
1018680 2024-07-10T08:25:02 Z bachhoangxuan Sweeping (JOI20_sweeping) C++17
100 / 100
 1954 ms 368324 KB 
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int maxn = 1500005;
struct Query{
    int t,id,x,y;
    Query(){}
    Query(int t=-1,int id=-1,int x=-1,int y=-1):t(t),id(id),x(x),y(y){}
};

int n,m,q;

int val[2*maxn],p[2*maxn],sz,f[maxn];
vector<int> cc[2*maxn];

int ss;
pii ans[maxn];

int add(int i,int v){
    val[++sz]=v,p[i]=sz;
    cc[sz]={i};
    return sz;
}
int unions(int a,int b){
    if((int)cc[a].size()<(int)cc[b].size()) swap(a,b);
    for(int id:cc[b]) p[id]=a,cc[a].push_back(id);
    cc[b].clear();
    return a;
}

void dnc(int l,int r,vector<Query> &qq){
    if(qq.empty()) return;
    int mid=(l+r)>>1;
    int X=mid,Y=n-mid;
    vector<Query> lq,rq;
    priority_queue<pii,vector<pii>,greater<pii>> px,py;
    sz=0;
    for(auto cq:qq){
        auto [t,id,x,y]=cq;
        if(t==1){
            if(f[id]==1) lq.push_back(cq);
            else if(f[id]==2) rq.push_back(cq);
            else ans[x]={val[p[id<<1]],val[p[id<<1|1]]};
        }
        else if(t==2){
            int d=x;
            if(d<Y){
                rq.push_back(cq);
                while(!py.empty() && py.top().fi<=d){
                    int cur=py.top().se;py.pop();
                    for(int id:cc[cur]){
                        if(!f[id>>1]){
                            f[id>>1]=2;
                            rq.push_back(Query(4,id>>1,n-d,val[cur]));
                        }
                    }
                }
            }
            else{
                int rt=0;
                while(!px.empty() && px.top().fi<=n-d){
                    int cur=px.top().se;px.pop();
                    rt=(rt?unions(rt,cur):cur);
                }
                if(rt) val[rt]=n-d,px.push({n-d,rt});
                lq.push_back(cq);
            }
        }
        else if(t==3){
            int d=x;
            if(d<X){
                lq.push_back(cq);
                while(!px.empty() && px.top().fi<=d){
                    int cur=px.top().se;px.pop();
                    for(int id:cc[cur]){
                        if(!f[id>>1]){
                            f[id>>1]=1;
                            lq.push_back(Query(4,id>>1,val[cur],n-d));
                        }
                    }
                }
            }
            else{
                int rt=0;
                while(!py.empty() && py.top().fi<=n-d){
                    int cur=py.top().se;py.pop();
                    rt=(rt?unions(rt,cur):cur);
                }
                if(rt) val[rt]=n-d,py.push({n-d,rt});
                rq.push_back(cq);
            }
        }
        else{

            if(x>X) f[id]=2,rq.push_back(cq);
            else if(y>Y) f[id]=1,lq.push_back(cq);
            else{
                f[id]=0;
                px.push({x,add(id<<1,x)});
                py.push({y,add(id<<1|1,y)});
            }
        }
    }
    if(l==r) return;
    if(l+1==r) dnc(r,r,rq);
    else dnc(l,mid,lq),dnc(mid,r,rq);

}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> m >> q;
    vector<Query> qq;
    for(int i=1;i<=m;i++){
        int x,y;cin >> x >> y;
        qq.push_back(Query(4,i,x,y));
    }
    for(int i=1;i<=q;i++){
        int t;cin >> t;
        if(t==1){
            int id;cin >> id;
            qq.push_back(Query(1,id,++ss,-1));
        }
        else if(t<=3){
            int d;cin >> d;
            qq.push_back(Query(t,-1,d,-1));
        }
        else{
            int x,y;cin >> x >> y;
            qq.push_back(Query(4,++m,x,y));
        }
    }
    dnc(0,n,qq);
    for(int i=1;i<=ss;i++) cout << ans[i].fi << ' ' << ans[i].se << '\n';
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 72964 KB Output is correct
2 Correct 27 ms 72652 KB Output is correct
3 Correct 25 ms 72704 KB Output is correct
4 Correct 29 ms 72980 KB Output is correct
5 Correct 28 ms 72800 KB Output is correct
6 Correct 24 ms 72796 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1407 ms 207676 KB Output is correct
2 Correct 1333 ms 196968 KB Output is correct
3 Correct 1294 ms 204868 KB Output is correct
4 Correct 1156 ms 246344 KB Output is correct
5 Correct 1756 ms 235292 KB Output is correct
6 Correct 1610 ms 237544 KB Output is correct
7 Correct 1433 ms 204624 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1215 ms 226956 KB Output is correct
2 Correct 1326 ms 222620 KB Output is correct
3 Correct 1030 ms 232116 KB Output is correct
4 Correct 1379 ms 306140 KB Output is correct
5 Correct 1345 ms 275056 KB Output is correct
6 Correct 1182 ms 220792 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1215 ms 226956 KB Output is correct
2 Correct 1326 ms 222620 KB Output is correct
3 Correct 1030 ms 232116 KB Output is correct
4 Correct 1379 ms 306140 KB Output is correct
5 Correct 1345 ms 275056 KB Output is correct
6 Correct 1182 ms 220792 KB Output is correct
7 Correct 1331 ms 211068 KB Output is correct
8 Correct 1395 ms 220708 KB Output is correct
9 Correct 1303 ms 211872 KB Output is correct
10 Correct 1206 ms 243508 KB Output is correct
11 Correct 1561 ms 268600 KB Output is correct
12 Correct 1585 ms 259192 KB Output is correct
13 Correct 1666 ms 364048 KB Output is correct
14 Correct 134 ms 131840 KB Output is correct
15 Correct 407 ms 172648 KB Output is correct
16 Correct 1312 ms 217252 KB Output is correct
17 Correct 1283 ms 222324 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 72964 KB Output is correct
2 Correct 27 ms 72652 KB Output is correct
3 Correct 25 ms 72704 KB Output is correct
4 Correct 29 ms 72980 KB Output is correct
5 Correct 28 ms 72800 KB Output is correct
6 Correct 24 ms 72796 KB Output is correct
7 Correct 1407 ms 207676 KB Output is correct
8 Correct 1333 ms 196968 KB Output is correct
9 Correct 1294 ms 204868 KB Output is correct
10 Correct 1156 ms 246344 KB Output is correct
11 Correct 1756 ms 235292 KB Output is correct
12 Correct 1610 ms 237544 KB Output is correct
13 Correct 1433 ms 204624 KB Output is correct
14 Correct 1215 ms 226956 KB Output is correct
15 Correct 1326 ms 222620 KB Output is correct
16 Correct 1030 ms 232116 KB Output is correct
17 Correct 1379 ms 306140 KB Output is correct
18 Correct 1345 ms 275056 KB Output is correct
19 Correct 1182 ms 220792 KB Output is correct
20 Correct 1331 ms 211068 KB Output is correct
21 Correct 1395 ms 220708 KB Output is correct
22 Correct 1303 ms 211872 KB Output is correct
23 Correct 1206 ms 243508 KB Output is correct
24 Correct 1561 ms 268600 KB Output is correct
25 Correct 1585 ms 259192 KB Output is correct
26 Correct 1666 ms 364048 KB Output is correct
27 Correct 134 ms 131840 KB Output is correct
28 Correct 407 ms 172648 KB Output is correct
29 Correct 1312 ms 217252 KB Output is correct
30 Correct 1283 ms 222324 KB Output is correct
31 Correct 1250 ms 238100 KB Output is correct
32 Correct 1326 ms 214392 KB Output is correct
33 Correct 1345 ms 185076 KB Output is correct
34 Correct 1447 ms 218860 KB Output is correct
35 Correct 1443 ms 213368 KB Output is correct
36 Correct 1167 ms 232312 KB Output is correct
37 Correct 1954 ms 368324 KB Output is correct
38 Correct 1773 ms 363224 KB Output is correct
39 Correct 1567 ms 323948 KB Output is correct
40 Correct 1291 ms 212024 KB Output is correct