Submission #1026186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026186		Vanio	Segments (IZhO18_segments)	C++17	100 / 100	1868 ms	16364 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[5001];

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

int n,segbr,t,nextSegmentId,lastans,bsz=2000,bbr,qbStart=1;
vector<int> segmentIds;
bool F[200001];

void buildStructure(){
    int i=1;
    segbr=0;
    vector<int> neww;
    for(int it : segmentIds){
        if(F[it]==0){neww.push_back(it); tseg[i]=seg[it]; ++i;segbr++;}

    }
    segmentIds=neww;

    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.push_back(nextSegmentId);
}

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

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;
//qbsz=sqrt(n);

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:28: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
    3 | #pragma GCC optimize("avx2")
      |                            ^
segments.cpp:12:30: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   12 | bool fff(segment p, segment q){
      |                              ^
segments.cpp:31:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   31 | void buildStructure(){
      |                     ^
segments.cpp:69:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   69 | void handleQt1(int k){
      |                     ^
segments.cpp:80:21: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   80 | void handleQt2(int k){
      |                     ^
segments.cpp:86:22: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   86 | void handleQt3(int ti){
      |                      ^
segments.cpp:133:10: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
  133 | int main()
      |          ^
segments.cpp: In function 'int main()':
segments.cpp:139:10: warning: unused variable 'l' [-Wunused-variable]
  139 | int i,qt,l,r,id,k,f=0,qbsz=2000;
      |          ^
segments.cpp:139:12: warning: unused variable 'r' [-Wunused-variable]
  139 | int i,qt,l,r,id,k,f=0,qbsz=2000;
      |            ^
segments.cpp:139:14: warning: unused variable 'id' [-Wunused-variable]
  139 | int i,qt,l,r,id,k,f=0,qbsz=2000;
      |              ^~
segments.cpp:139:17: warning: unused variable 'k' [-Wunused-variable]
  139 | int i,qt,l,r,id,k,f=0,qbsz=2000;
      |                 ^
segments.cpp:139:19: warning: unused variable 'f' [-Wunused-variable]
  139 | 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