Submission #660095

#TimeUsernameProblemLanguageResultExecution timeMemory
660095KarukEvent Hopping (BOI22_events)C++14
20 / 100
192 ms29624 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>b?a:b; } const int k=(1<<30); 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]; pair<int,int> prev[n][25]; vector<pair<pair<int,int>,int>>v; for(int i=0;i<n;i++) { int x,y; cin>>x>>y; a[i]={x,y}; v.push_back({{x,1},i}); v.push_back({{y,2},i}); } sort(v.begin(),v.end()); set<pair<int,int>>smalleststart; for(auto i:v) { if(i.first.second==2) { smalleststart.erase({a[i.second].first,i.second}); } else { smalleststart.insert({i.first.first,i.second}); prev[i.second][0]=(*smalleststart.begin()); } } ///coord1,isbeginning,index for(int j=1;j<25;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=24;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
#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...