Submission #1023314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023314		Vanio	Segments (IZhO18_segments)	C++17	0 / 100	457 ms	6448 KiB

segments

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

struct segment{
    int l,r;
};
segment seg[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 l,r,k;
};
query qs[200001];

int n,m,t,nextSegmentId,lastans,bsz;
set<int> segmentIds;

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

int i,qt,l,r,id,k,f=0;
cin>>n>>t;
for(i=1;i<=n;i++){
    cin>>qt;
    if(qt==1){
        cin>>seg[i].l>>seg[i].r;
        if(seg[i].l>seg[i].r) swap(seg[i].l,seg[i].r);
    }
    else{
        if(f==0){
            m=i-1;
            f=1;
        }
        cin>>qs[i].l>>qs[i].r>>qs[i].k;
        if(qs[i].l>qs[i].r) swap(qs[i].l,qs[i].r);
    }
}

sort(seg+1,seg+1+m,fff);
bsz=sqrt(m);
if(bsz*bsz<m) bsz++;
int bindx;
for(i=1;i<=m;i++){
    bindx=(i-1)/bsz;
    b[bindx].mi=min(b[bindx].mi,seg[i].r-seg[i].l+1);
    b[bindx].ma=max(b[bindx].ma,seg[i].r-seg[i].l+1);
    b[bindx].vl.push_back(seg[i].l);
    b[bindx].vr.push_back(seg[i].r);
}

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

int ans,j,g;
for(i=m+1;i<=n;i++){
    ans=m;
    qs[i].l^=lastans*t;
    qs[i].r^=lastans*t;
    if(qs[i].l>qs[i].r) swap(qs[i].l,qs[i].r);
    for(j=0;j<bsz;j++){
        if(b[j].mi>=qs[i].k-1){
            auto it = lower_bound(b[j].vl.begin(),b[j].vl.end(),qs[i].r-qs[i].k+2);
            ans-=b[j].vl.end()-it;
            auto it2 = upper_bound(b[j].vr.begin(),b[j].vr.end(),qs[i].l+qs[i].k-2);
            ans-=it2-b[j].vr.begin();
        }
        else if(b[j].mi<qs[i].k-1 && qs[i].k-1<=b[j].ma){
            for(g=j*bsz+1;g<=(j+1)*bsz;g++){
                if(seg[g].r-seg[g].l+1<qs[i].k || seg[g].l>=qs[i].r-qs[i].k+2 || seg[g].r<=qs[i].l+qs[i].k-2) ans--;
            }
        }
        else{
            ans-=m-bsz*j;
            break;
        }
    }
    lastans=ans;
    cout<<ans<<'\n';
}

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

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:32:10: warning: unused variable 'l' [-Wunused-variable]
   32 | int i,qt,l,r,id,k,f=0;
      |          ^
segments.cpp:32:12: warning: unused variable 'r' [-Wunused-variable]
   32 | int i,qt,l,r,id,k,f=0;
      |            ^
segments.cpp:32:14: warning: unused variable 'id' [-Wunused-variable]
   32 | int i,qt,l,r,id,k,f=0;
      |              ^~
segments.cpp:32:17: warning: unused variable 'k' [-Wunused-variable]
   32 | int i,qt,l,r,id,k,f=0;
      |                 ^

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