# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
896411 | Abdalaziz_Alshami | Event Hopping (BOI22_events) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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; }}