답안 #1023261

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1023261	2024-07-14T14:23:22 Z	Vanio	Segments (IZhO18_segments)	C++17	컴파일 오류	0 ms	0 KB

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,ans,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);
    }
}
if(f==0){
    m=i-1;
    f=1;
}

sort(segments+1,segments+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;
    for(j=0;j<bsz;j++){
        if(b[j].mi>=qs[i].k){
            auto it = lower_bound(b[j].vl.begin(),b[j].vl.end(),seg[i].r-seg[i].k+2);
            ans-=b[j].vl.end()-it;
            auto it = upper_bound(b[j].vr.begin(),b[j].vr.end(),seg[i].l+seg[i].k-2);
            ans-=it-b[j].vr.begin();
        }
        else if(b[j].mi<qs[i].k && qs[i].k<=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>=seg[i].r-seg[i].k+2 || seg[g].r<=seg[i].l+seg[i].k-2) ans--;
            }
        }
        else{
            ans-=m-bsz*j;
            break;
        }
    }
    cout<<ans<<'\n';
}



auto it = lower_bound(v.begin(),v.end(),4);
cout<<v.end()-it;

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

Compilation message

segments.cpp: In function 'int main()':
segments.cpp:54:6: error: 'segments' was not declared in this scope; did you mean 'segment'?
   54 | sort(segments+1,segments+1+m,fff);
      |      ^~~~~~~~
      |      segment
segments.cpp:71:5: error: redeclaration of 'int ans'
   71 | int ans,j,g;
      |     ^~~
segments.cpp:32:19: note: 'int ans' previously declared here
   32 | int i,qt,l,r,id,k,ans,f=0;
      |                   ^~~
segments.cpp:76:81: error: 'struct segment' has no member named 'k'
   76 |             auto it = lower_bound(b[j].vl.begin(),b[j].vl.end(),seg[i].r-seg[i].k+2);
      |                                                                                 ^
segments.cpp:78:81: error: 'struct segment' has no member named 'k'
   78 |             auto it = upper_bound(b[j].vr.begin(),b[j].vr.end(),seg[i].l+seg[i].k-2);
      |                                                                                 ^
segments.cpp:83:77: error: 'struct segment' has no member named 'k'
   83 |                 if(seg[g].r-seg[g].l+1<qs[i].k || seg[g].l>=seg[i].r-seg[i].k+2 || seg[g].r<=seg[i].l+seg[i].k-2) ans--;
      |                                                                             ^
segments.cpp:83:110: error: 'struct segment' has no member named 'k'
   83 |                 if(seg[g].r-seg[g].l+1<qs[i].k || seg[g].l>=seg[i].r-seg[i].k+2 || seg[g].r<=seg[i].l+seg[i].k-2) ans--;
      |                                                                                                              ^
segments.cpp:96:23: error: 'v' was not declared in this scope
   96 | auto it = lower_bound(v.begin(),v.end(),4);
      |                       ^
segments.cpp:32:10: warning: unused variable 'l' [-Wunused-variable]
   32 | int i,qt,l,r,id,k,ans,f=0;
      |          ^
segments.cpp:32:12: warning: unused variable 'r' [-Wunused-variable]
   32 | int i,qt,l,r,id,k,ans,f=0;
      |            ^
segments.cpp:32:14: warning: unused variable 'id' [-Wunused-variable]
   32 | int i,qt,l,r,id,k,ans,f=0;
      |              ^~
segments.cpp:32:17: warning: unused variable 'k' [-Wunused-variable]
   32 | int i,qt,l,r,id,k,ans,f=0;
      |                 ^