# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
896411 | Abdalaziz_Alshami | Event Hopping (BOI22_events) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>#include<set>#include<map>#include<utility>#define st first#define ed second//#define int int64_t#define endl '\n'using namespace std;signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,q; cin>>n>>q; pair<int,int>a[n+1]; map<int,int>pres; for(int i=1;i<=n;i++) { cin>>a[i].st>>a[i].ed; pres[a[i].st]; pres[a[i].ed]; } int d=1; for(auto &e:pres) e.ed=d,d++; set<int> m[d+10]; for(int i=1; i<=n;i++) { a[i].st=pres[a[i].st]; a[i].ed=pres[a[i].ed]; m[a[i].st].insert(-a[i].ed); } while(q--) { int u,v; cin>>u>>v; if(u==v) { cout<<0<<endl; continue;} int i=a[u].st,mx=a[u].ed,g1=a[v].st,g2=a[v].ed,p=-1,ans=0; bool f=false; while(i<=mx) { auto it=m[i].lower_bound(-g2); if(it!=m[i].end()) p=max(p,-*it); if(i==mx){ mx=p; ans++; if(mx<=g2&&i>=g1) { f=true; break;} } i++; } if(f) cout<<ans<<endl; else cout<<"impossible"<<endl; }}