oj.uz

Submission #261250

# Submission time Handle Problem Language Result Execution time Memory
261250 2020-08-11T15:25:13 Z mhy908 Sweeping (JOI20_sweeping) C++14
100 / 100
 10569 ms 1627832 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;

pair<pii, int> rng[1500010];
int n, m, q, re;

struct SWP_SEG{
    struct NODE{
        NODE *lc, *rc;
        NODE(){lc=rc=0;}
        map<int, vector<int> > l, r;
        vector<int> lnum, rnum, rv, ch;
        struct INC_DSU{
           vector<int> par;
           void ins(){int sz=par.size(); par.eb(sz);}
           int findpar(int num){return num==par[num]?num:par[num]=findpar(par[num]);}
           void mergepar(int a, int b){par[findpar(a)]=findpar(b);}
        }ufl, ufr;
        pii get_range(int num){
            int ul=ufl.findpar(num);
            int ur=ufr.findpar(num);
            return mp(lnum[ul], rnum[ur]);
        }
        void ins(int s, int e, pii rn, int num){
            rng[num]=mp(mp(s, e), lnum.size());
            rv.eb(num);
            ufl.ins(); ufr.ins();
            lnum.eb(rn.F); rnum.eb(rn.S); ch.eb(0);
            if(l[rn.F].size())ufl.mergepar(rng[num].S, l[rn.F].back());
            if(r[rn.S].size())ufr.mergepar(rng[num].S, r[rn.S].back());
            l[rn.F].eb(rng[num].S); r[rn.S].eb(rng[num].S);
        }
    }*rt;
    SWP_SEG(){rt=new NODE();}
    pii query(NODE *nd, int s, int e, int num){
        if(s==rng[num].F.F&&e==rng[num].F.S)return nd->get_range(rng[num].S);
        if(rng[num].F.S<=(s+e)/2)return query(nd->lc, s, (s+e)/2, num);
        return query(nd->rc, (s+e)/2+1, e, num);
    }
    void overkill_lft(NODE *nd, int s, int e, int num){
        vector<pair<pii, int> > vc;
        auto it=nd->r.end();
        while(it!=nd->r.begin()){
            it--;
            if(it->F<num){
                it++;
                break;
            }
            for(auto i:it->S){
                if(nd->ch[i])continue;
                nd->ch[i]=1;
                vc.eb(mp(num, it->F), i);
            }
        }
        nd->r.erase(it, nd->r.end());
        if(vc.size()==0)return;
        if(!nd->rc)nd->rc=new NODE();
        for(auto i:vc)upd_ins(nd->rc, (s+e)/2+1, e, i.F, nd->rv[i.S]);
    }
    void overkill_rgt(NODE *nd, int s, int e, int num){
        vector<pair<pii, int> > vc;
        auto it=nd->l.begin();
        while(it!=nd->l.end()){
            if(it->F>num)break;
            for(auto i:it->S){
                if(nd->ch[i])continue;
                nd->ch[i]=1;
                vc.eb(mp(it->F, num), i);
            }
            it++;
        }
        nd->l.erase(nd->l.begin(), it);
        if(vc.size()==0)return;
        if(!nd->lc)nd->lc=new NODE();
        for(auto i:vc)upd_ins(nd->lc, s, (s+e)/2, i.F, nd->rv[i.S]);
    }
    void push_lft(NODE *nd, int s, int e, int num){
        if(nd->l.size()==0)return;
        if(nd->l.begin()->F>num)return;
        auto it=nd->l.begin();
        auto it2=nd->l.begin();
        it2++;
        while(it2!=nd->l.end()){
            if(it2->F>num)break;
            if(it->S.size()>it2->S.size())swap(it->S, it2->S);
            for(auto i:it->S){
                nd->ufl.mergepar(i, it2->S.back());
                it2->S.eb(i);
            }
            it++; it2++;
        }
        nd->lnum[nd->ufl.findpar(it->S.back())]=num;
        swap(it->S, nd->l[num]);
        nd->l.erase(nd->l.begin(), nd->l.find(num));
    }
    void push_rgt(NODE *nd, int s, int e, int num){
        if(nd->r.size()==0)return;
        if(nd->r.rbegin()->F<num)return;
        auto it=nd->r.end();
        auto it2=nd->r.end();
        it--;
        it2--;
        if(it2!=nd->r.begin())it2--;
        while(it!=nd->r.begin()){
            if(it2->F<num)break;
            if(it->S.size()>it2->S.size())swap(it->S, it2->S);
            for(auto i:it->S){
                nd->ufr.mergepar(i, it2->S.back());
                it2->S.eb(i);
            }
            it--; it2--;
        }
        nd->rnum[nd->ufr.findpar(it->S.back())]=num;
        swap(it->S, nd->r[num]);
        nd->r.erase(++(nd->r.find(num)), nd->r.end());
    }
    void upd_ins(NODE *nd, int s, int e, pii rn, int num){
        int mid=(s+e)/2;
        if((rn.F<=mid&&mid<rn.S)||s==e){
            nd->ins(s, e, rn, num);
            return;
        }
        if(rn.S<=mid){
            if(!nd->lc)nd->lc=new NODE();
            upd_ins(nd->lc, s, (s+e)/2, rn, num);
        }
        else{
            if(!nd->rc)nd->rc=new NODE();
            upd_ins(nd->rc, (s+e)/2+1, e, rn, num);
        }
    }
    void upd_swpl(NODE *nd, int s, int e, int num){
        if(s==e)return;
        int mid=(s+e)/2;
        if(num>mid){
            overkill_lft(nd, s, e, num);
            if(nd->rc)upd_swpl(nd->rc, (s+e)/2+1, e, num);
        }
        else{
            push_lft(nd, s, e, num);
            if(nd->lc)upd_swpl(nd->lc, s, (s+e)/2, num);
        }
    }
    void upd_swpr(NODE *nd, int s, int e, int num){
        if(s==e)return;
        int mid=(s+e)/2;
        if(num<=mid){
            overkill_rgt(nd, s, e, num);
            if(nd->lc)upd_swpr(nd->lc, s, (s+e)/2, num);
        }
        else{
            push_rgt(nd, s, e, num);
            if(nd->rc)upd_swpr(nd->rc, (s+e)/2+1, e, num);
        }
    }
    void upd_ins(pii rn, int num){
        rn.S=n-rn.S;
        upd_ins(rt, 0, n, rn, num);
    }
    void upd_swpl(int num){upd_swpl(rt, 0, n, num);}
    void upd_swpr(int num){upd_swpr(rt, 0, n, num);}
    pii query(int num){
        pii tmp=query(rt, 0, n, num);
        tmp.S=n-tmp.S;
        return tmp;
    }
}seg;

int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=m; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        seg.upd_ins(mp(a, b), ++re);
    }
    for(int i=1; i<=q; i++){
        int a;
        scanf("%d", &a);
        if(a==1){
            int b;
            scanf("%d", &b);
            pii ans=seg.query(b);
            printf("%d %d\n", ans.F, ans.S);
        }
        if(a==2){
            int b;
            scanf("%d", &b);
            seg.upd_swpl(n-b);
        }
        if(a==3){
            int b;
            scanf("%d", &b);
            seg.upd_swpr(b);
        }
        if(a==4){
            int b, c;
            scanf("%d %d", &b, &c);
            seg.upd_ins(mp(b, c), ++re);
        }
    }
}

Compilation message

sweeping.cpp: In function 'int main()':
sweeping.cpp:179:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:182:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~
sweeping.cpp:187:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
         ~~~~~^~~~~~~~~~
sweeping.cpp:190:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &b);
             ~~~~~^~~~~~~~~~
sweeping.cpp:196:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &b);
             ~~~~~^~~~~~~~~~
sweeping.cpp:201:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &b);
             ~~~~~^~~~~~~~~~
sweeping.cpp:206:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d", &b, &c);
             ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2176 KB Output is correct
2 Correct 7 ms 1024 KB Output is correct
3 Correct 8 ms 1536 KB Output is correct
4 Correct 11 ms 1536 KB Output is correct
5 Correct 12 ms 1664 KB Output is correct
6 Correct 3 ms 640 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7883 ms 747208 KB Output is correct
2 Correct 7195 ms 735664 KB Output is correct
3 Correct 7643 ms 736100 KB Output is correct
4 Correct 5589 ms 421444 KB Output is correct
5 Correct 10569 ms 516080 KB Output is correct
6 Correct 10370 ms 493760 KB Output is correct
7 Correct 6844 ms 705712 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3234 ms 229968 KB Output is correct
2 Correct 2446 ms 177124 KB Output is correct
3 Correct 2557 ms 325712 KB Output is correct
4 Correct 3949 ms 374492 KB Output is correct
5 Correct 3140 ms 198264 KB Output is correct
6 Correct 2128 ms 145876 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3234 ms 229968 KB Output is correct
2 Correct 2446 ms 177124 KB Output is correct
3 Correct 2557 ms 325712 KB Output is correct
4 Correct 3949 ms 374492 KB Output is correct
5 Correct 3140 ms 198264 KB Output is correct
6 Correct 2128 ms 145876 KB Output is correct
7 Correct 5907 ms 534064 KB Output is correct
8 Correct 5649 ms 530608 KB Output is correct
9 Correct 5795 ms 532400 KB Output is correct
10 Correct 5296 ms 349004 KB Output is correct
11 Correct 8132 ms 342540 KB Output is correct
12 Correct 6494 ms 234516 KB Output is correct
13 Correct 6178 ms 240684 KB Output is correct
14 Correct 240 ms 4216 KB Output is correct
15 Correct 2757 ms 100220 KB Output is correct
16 Correct 5956 ms 537248 KB Output is correct
17 Correct 5231 ms 527228 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2176 KB Output is correct
2 Correct 7 ms 1024 KB Output is correct
3 Correct 8 ms 1536 KB Output is correct
4 Correct 11 ms 1536 KB Output is correct
5 Correct 12 ms 1664 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 7883 ms 747208 KB Output is correct
8 Correct 7195 ms 735664 KB Output is correct
9 Correct 7643 ms 736100 KB Output is correct
10 Correct 5589 ms 421444 KB Output is correct
11 Correct 10569 ms 516080 KB Output is correct
12 Correct 10370 ms 493760 KB Output is correct
13 Correct 6844 ms 705712 KB Output is correct
14 Correct 3234 ms 229968 KB Output is correct
15 Correct 2446 ms 177124 KB Output is correct
16 Correct 2557 ms 325712 KB Output is correct
17 Correct 3949 ms 374492 KB Output is correct
18 Correct 3140 ms 198264 KB Output is correct
19 Correct 2128 ms 145876 KB Output is correct
20 Correct 5907 ms 534064 KB Output is correct
21 Correct 5649 ms 530608 KB Output is correct
22 Correct 5795 ms 532400 KB Output is correct
23 Correct 5296 ms 349004 KB Output is correct
24 Correct 8132 ms 342540 KB Output is correct
25 Correct 6494 ms 234516 KB Output is correct
26 Correct 6178 ms 240684 KB Output is correct
27 Correct 240 ms 4216 KB Output is correct
28 Correct 2757 ms 100220 KB Output is correct
29 Correct 5956 ms 537248 KB Output is correct
30 Correct 5231 ms 527228 KB Output is correct
31 Correct 5763 ms 638900 KB Output is correct
32 Correct 6921 ms 633336 KB Output is correct
33 Correct 5116 ms 1627832 KB Output is correct
34 Correct 7609 ms 753404 KB Output is correct
35 Correct 7736 ms 754708 KB Output is correct
36 Correct 5530 ms 352740 KB Output is correct
37 Correct 9232 ms 441792 KB Output is correct
38 Correct 7533 ms 242480 KB Output is correct
39 Correct 7029 ms 229356 KB Output is correct
40 Correct 6200 ms 593776 KB Output is correct