Submission #261250

#	Time	Username	Problem	Language	Result	Execution time	Memory
261250		mhy908	Sweeping (JOI20_sweeping)	C++14	100 / 100	10569 ms	1627832 KiB

sweeping

#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 (stderr)

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 / 1
• Subtask 2: 10 / 10
• Subtask 3: 11 / 11
• Subtask 4: 53 / 53
• Subtask 5: 25 / 25