oj.uz

Submission #1023417

# Submission time Handle Problem Language Result Execution time Memory
1023417 2024-07-14T18:11:12 Z Vanio Segments (IZhO18_segments) C++17
15 / 100
 518 ms 6740 KB 
#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-1);
            //cout<<m-bsz*(j-1)<<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 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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 484 ms 3416 KB Output is correct
2 Correct 492 ms 6228 KB Output is correct
3 Correct 505 ms 6224 KB Output is correct
4 Correct 498 ms 6224 KB Output is correct
5 Correct 148 ms 6608 KB Output is correct
6 Correct 110 ms 6740 KB Output is correct
7 Correct 506 ms 6228 KB Output is correct
8 Correct 518 ms 6228 KB Output is correct
9 Correct 500 ms 6224 KB Output is correct
10 Correct 487 ms 6224 KB Output is correct
11 Correct 496 ms 6172 KB Output is correct
12 Correct 408 ms 6716 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 3268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 89 ms 3412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -