Submission #1026197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026197		Vanio	Segments (IZhO18_segments)	C++17	100 / 100	1839 ms	17352 KiB

segments

    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("avx2")

    #include<bits/stdc++.h>
    using namespace std;

    struct segment{
        int l,r;
    };
    segment seg[200001],tseg[200001];
    bool fff(segment p, segment q){
        return p.r-p.l>q.r-q.l;
    }

    struct block{
        int mi=INT_MAX,ma=-1;
        vector<int> vl,vr;
    };
    block b[501];

    struct query{
        int qt,id,l,r,k;
    };
    query qs[200001];

    int n,segbr,t,nextSegmentId,lastans,bsz=2000,bbr,qbStart=1;
    set<int> segmentIds;

    void buildStructure(){
        int i=1;
        segbr=segmentIds.size();
        for(int it : segmentIds){
            tseg[i]=seg[it];
            i++;
        }

        sort(tseg+1,tseg+1+segbr,fff);
        //bsz=sqrt(segbr)+1;
        bbr=segbr/bsz;
        if(segbr%bsz>0) bbr++;
        int bindx=0;
        for(i=1;i<=segbr;i++){
            if(i%bsz==1) bindx++;
            b[bindx].mi=INT_MAX;
            b[bindx].ma=-1;
            b[bindx].vl.clear();
            b[bindx].vr.clear();
        }
        bindx=0;
        for(i=1;i<=segbr;i++){
            if(i%bsz==1) bindx++;
            //cout<<bindx<<" "<<seg[i].l<<" "<<seg[i].r<<'\n';
            b[bindx].mi=min(b[bindx].mi,tseg[i].r-tseg[i].l+1);
            b[bindx].ma=max(b[bindx].ma,tseg[i].r-tseg[i].l+1);
            b[bindx].vl.push_back(tseg[i].l);
            b[bindx].vr.push_back(tseg[i].r);
        }

        for(i=1;i<=bbr;i++){
            sort(b[i].vl.begin(),b[i].vl.end());
            sort(b[i].vr.begin(),b[i].vr.end());
        }
    }

    void handleQt1(int k){
        nextSegmentId++;
        qs[k].qt=1;
        qs[k].id=nextSegmentId;
        cin>>seg[nextSegmentId].l>>seg[nextSegmentId].r;
        seg[nextSegmentId].l^=lastans*t;
        seg[nextSegmentId].r^=lastans*t;
        if(seg[nextSegmentId].l>seg[nextSegmentId].r) swap(seg[nextSegmentId].l,seg[nextSegmentId].r);
        segmentIds.insert(nextSegmentId);
    }

    void handleQt2(int k){
        qs[k].qt=2;
        cin>>qs[k].id;
        segmentIds.erase(qs[k].id);
    }

    void handleQt3(int ti){
        int l,r,k,ans=0,j,i;
        cin>>l>>r>>k;

        ans=segbr;
        l^=lastans*t;
        r^=lastans*t;
        if(l>r) swap(l,r);

        //cout<<"qt3 "<<l<<" "<<r<<" "<<k<<endl;
        for(i=1;i<=bbr;i++){
            if(b[i].mi>=k){
                auto it = lower_bound(b[i].vl.begin(),b[i].vl.end(),r-k+2);
                //cout<<"1 "<<b[i].vl.end()-it<<endl;
                ans-=b[i].vl.end()-it;
                auto it2 = upper_bound(b[i].vr.begin(),b[i].vr.end(),l+k-2);
                //cout<<"1 "<<it2-b[i].vr.begin()<<endl;
                ans-=it2-b[i].vr.begin();
            }
            else if(b[i].mi<k && k<=b[i].ma){
                for(j=(i-1)*bsz+1;j<=i*bsz && j<=segbr;j++){
                    if(tseg[j].r-tseg[j].l+1<k || tseg[j].l>=r-k+2 || tseg[j].r<=l+k-2){ans--; /*cout<<"2 "<<j<<" "<<seg[j].l<<" "<<seg[j].r<<endl;*/}
                }
            }
            else{
                ans-=segbr-bsz*(i-1);
                //cout<<segbr-bsz*(i-1)<<endl;
                break;
            }
        }

        int segId;
        for(i=ti-1;i>=qbStart;i--){
            if(qs[i].qt==1){
                segId=qs[i].id;
                if(min(r,seg[segId].r)-max(l,seg[segId].l)+1>=k) ans++;
            }
            if(qs[i].qt==2){
                segId=qs[i].id;
                if(min(r,seg[segId].r)-max(l,seg[segId].l)+1>=k) ans--;
            }
        }

        lastans=ans;
        cout<<ans<<'\n';
    }

    int main()
    {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int i,qt,l,r,id,k,f=0,qbsz=2000;
    cin>>n>>t;

    for(i=1;i<=n;i++){
        if(i%qbsz==1){
            buildStructure();
            qbStart=i;
            //cout<<"new query block "<<i<<" "<<segbr<<endl;
        }

        cin>>qt;
        if(qt==1) handleQt1(i);
        if(qt==2) handleQt2(i);
        if(qt==3) handleQt3(i);
    }

    return 0;
    }
    /*
    6 1
    1 1 2
    1 3 8
    1 5 8
    1 2 4
    1 8 10
    3 3 7 2

    25 1
    1 97 61
    1 21 92
    1 57 10
    1 77 46
    1 60 54
    1 34 35
    1 7 66
    1 71 61
    1 64 19
    1 22 80
    1 81 39
    1 57 52
    1 9 4
    1 17 28
    1 16 51
    1 67 2
    1 25 51
    1 42 83
    1 61 65
    1 37 45
    3 31 34 2
    3 36 37 1
    3 44 62 8
    3 65 67 3
    3 84 92 6

    8   8
    11  11
    16  11
    3   6
    2   2
    */

Compilation message (stderr)

segments.cpp:3:32: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
    3 |     #pragma GCC optimize("avx2")
      |                                ^
segments.cpp:12:34: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   12 |     bool fff(segment p, segment q){
      |                                  ^
segments.cpp:30:25: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   30 |     void buildStructure(){
      |                         ^
segments.cpp:66:25: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   66 |     void handleQt1(int k){
      |                         ^
segments.cpp:77:25: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   77 |     void handleQt2(int k){
      |                         ^
segments.cpp:83:26: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   83 |     void handleQt3(int ti){
      |                          ^
segments.cpp:130:14: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  130 |     int main()
      |              ^
segments.cpp: In function 'int main()':
segments.cpp:136:14: warning: unused variable 'l' [-Wunused-variable]
  136 |     int i,qt,l,r,id,k,f=0,qbsz=2000;
      |              ^
segments.cpp:136:16: warning: unused variable 'r' [-Wunused-variable]
  136 |     int i,qt,l,r,id,k,f=0,qbsz=2000;
      |                ^
segments.cpp:136:18: warning: unused variable 'id' [-Wunused-variable]
  136 |     int i,qt,l,r,id,k,f=0,qbsz=2000;
      |                  ^~
segments.cpp:136:21: warning: unused variable 'k' [-Wunused-variable]
  136 |     int i,qt,l,r,id,k,f=0,qbsz=2000;
      |                     ^
segments.cpp:136:23: warning: unused variable 'f' [-Wunused-variable]
  136 |     int i,qt,l,r,id,k,f=0,qbsz=2000;
      |                       ^

• Subtask 1: 7 / 7
• Subtask 2: 15 / 15
• Subtask 3: 16 / 16
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20
• Subtask 6: 25 / 25