Submission #660109

#TimeUsernameProblemLanguageResultExecution timeMemory
660109KarukEvent Hopping (BOI22_events)C++14
100 / 100
262 ms34072 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; pair<int,int>max(pair<int,int>a,pair<int,int>b) { return a.first>b.first?a:b; } const int k=(1<<20); pair<int,int>maxv[k*2+1]; void upd(int x,int va,int ind) { pair<int,int>val={va,ind}; while(x>0) { maxv[x]=max(maxv[x],val); x>>=1; } } pair<int,int> ask(int &from,int &to,int cur=1,int beg=0,int en=k-1) { if(from<=beg && en<=to)return maxv[cur]; if(to<beg || en<from)return {-1,-1}; int mid=(beg+en)>>1; return max(ask(from,to,cur<<1,beg,mid),ask(from,to,(cur<<1)|1,mid+1,en)); } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n,q;cin>>n>>q; pair<int,int>a[n]; vector<int>v; for(int i=0;i<n;i++) { int x,y; cin>>x>>y; v.push_back(x); v.push_back(y); a[i]={x,y}; } sort(v.begin(),v.end()); map<int,int>m; for(int i=0;i<v.size();i++)m[v[i]]=i; for(int i=0;i<n;i++) { int x,y; a[i].first=m[a[i].first]; a[i].second=m[a[i].second]; x=a[i].first; y=a[i].second; upd(y+k,k-x,i); } pair<int,int> prev[n][20]; for(int i=0;i<n;i++) { pair<int,int>d=ask(a[i].first,a[i].second); d.first=k-d.first; prev[i][0]=d; } for(int j=1;j<20;j++) { for(int i=0;i<n;i++) { prev[i][j]=prev[prev[i][j-1].second][j-1]; } } for(int i=0;i<q;i++) { int x,y;cin>>x>>y;x--;y--; if(x==y)cout<<0<<endl; else if(a[x].second>=a[y].first && a[x].second<=a[y].second)cout<<1<<endl; else if(a[x].second>a[y].second){cout<<"impossible"<<endl;} else { int cnt=0; int cur=y; int en=a[x].second; for(int j=19;j>=0;j--) { if(prev[cur][j].first>en) { cur=prev[cur][j].second; cnt+=(1<<j); } } if(prev[cur][0].first>en)cout<<"impossible"<<endl; else cout<<cnt+2<<endl; } } return 0; } ///9:30

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<v.size();i++)m[v[i]]=i;
      |                 ~^~~~~~~~~
#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...