Submission #649742

#TimeUsernameProblemLanguageResultExecution timeMemory
649742ToroTNEvent Hopping (BOI22_events)C++14
100 / 100
138 ms19192 KiB
#include<bits/stdc++.h> using namespace std; #define pb push_back #define X first #define Y second pair<int,int> seg[400005]; int n,t,s[100005],e[100005],l,r,x,y,idx[100005],it,p[100005][25],num,ex[100005],ans; vector<tuple<int,int,int> > v; void build(int tree,int st,int ed) { int md=(st+ed)/2; if(st==ed) { seg[tree]={get<1>(v[st]),st}; return; } build(2*tree,st,md); build(2*tree+1,md+1,ed); seg[tree]=max(seg[2*tree],seg[2*tree+1]); } pair<int,int> query(int tree,int st,int ed,int l,int r) { int md=(st+ed)/2; if(st>r||ed<l) { return {(int)-2e9,(int)-2e9}; } if(st>=l&&ed<=r)return seg[tree]; return max(query(2*tree,st,md,l,r),query(2*tree+1,md+1,ed,l,r)); } int main() { scanf("%d%d",&n,&t); for(int i=1;i<=n;i++) { scanf("%d%d",&s[i],&e[i]); v.pb({-e[i],-s[i],i}); } v.pb({-2e9,-2e9,-2e9}); sort(v.begin(),v.end()); for(int i=1;i<=n;i++) { idx[get<2>(v[i])]=i; l=get<0>(v[i]); r=get<1>(v[i]); //printf("%d %d %d\n",l,r,i); } build(1,1,n); for(int i=1;i<=n;i++) { it=lower_bound(v.begin(),v.end(),make_tuple(get<1>(v[i])+1,-2e9,-2e9))-v.begin()-1; num=query(1,1,n,i+1,it).Y; ex[i]=it; p[i][0]=num; //printf("itnum=%d %d\n",it,num); } for(int i=1;i<=n;i++) { if(p[i][0]<1||p[i][0]>n)p[i][0]=i; } for(int i=1;i<=20;i++) { for(int j=1;j<=n;j++) { p[j][i]=p[p[j][i-1]][i-1]; } } while(t--) { scanf("%d%d",&x,&y); if(x==y) { printf("0\n"); continue; } if(e[x]>e[y]) { printf("impossible\n"); continue; } x=idx[x]; y=idx[y]; ans=0; //printf("y=%d x=%d\n",y,x); for(int i=20;i>=0;i--) { //printf("%d\n",p[y][i]); if(p[y][i]<x&&ex[p[y][i]]<x) { if(y!=p[y][i]) { y=p[y][i]; ans+=(1<<i); } /*y=p[y][i]; ans+=(1<<i);*/ } //printf("%d %d\n",i,y); } if(x<=ex[y]) { printf("%d\n",ans+1); }else if(x<=ex[p[y][0]]) { printf("%d\n",ans+2); }else { printf("impossible\n"); } } }

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d%d",&n,&t);
      |     ~~~~~^~~~~~~~~~~~~~
events.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%d%d",&s[i],&e[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
events.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...