Submission #1023412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023412		Vanio	Segments (IZhO18_segments)	C++17	0 / 100	520 ms	5460 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,bbr;
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);
    }
}

//cout<<"----------------"<<endl;

sort(seg+1,seg+1+m,fff);
bsz=sqrt(m)+1;
bbr=m/bsz;
if(m%bsz>0) bbr++;
int bindx=0;
for(i=1;i<=m;i++){
    if(i%bsz==1) bindx++;
    //cout<<bindx<<" "<<seg[i].l<<" "<<seg[i].r<<'\n';
    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=1;i<=bbr;i++){
    sort(b[i].vl.begin(),b[i].vl.end());
    sort(b[i].vr.begin(),b[i].vr.end());
}

//cout<<endl;
/*for(i=1;i<=bbr;i++){
    cout<<i<<" "<<b[i].mi<<" "<<b[i].ma<<'\n';
    for(int ch : b[i].vl) cout<<ch<<" ";
    cout<<'\n';
    for(int ch : b[i].vr) cout<<ch<<" ";
    cout<<'\n';
}*/
//cout<<endl;

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);

    //cout<<qs[i].l<<" "<<qs[i].r<<" "<<qs[i].k<<endl;
    for(j=1;j<=bbr;j++){
        if(b[j].mi>=qs[i].k){
            auto it = lower_bound(b[j].vl.begin(),b[j].vl.end(),qs[i].r-qs[i].k+2);
            //cout<<"1 "<<b[j].vl.end()-it<<endl;
            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);
            //cout<<"1 "<<it2-b[j].vr.begin()<<endl;
            ans-=it2-b[j].vr.begin();
        }
        else if(b[j].mi<qs[i].k && qs[i].k<=b[j].ma){
            for(g=(j-1)*bsz+1;g<=j*bsz && g<=m;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--; /*cout<<"2 "<<g<<" "<<seg[g].l<<" "<<seg[g].r<<endl;*/}
            }
        }
        else{
            ans-=m-bsz*j;
            //cout<<m-bsz*j<<endl;
            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

25 0
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 11 28 4
3 36 40 2
3 47 57 6
3 57 65 1
3 72 82 5

9   9
10   10
9   10
14  14
6   6
*/

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