제출 #1098994

#제출 시각아이디문제언어결과실행 시간메모리
1098994epicci23Event Hopping (BOI22_events)C++17
20 / 100
152 ms27704 KiB
#include "bits/stdc++.h" #define int long long #define all(v) v.begin() , v.end() #define sz(a) (int)a.size() using namespace std; const int N = 2e5 + 5; const int LOG = 20; vector<array<int,2>> v(N); vector<int> zip; int seg[4*N],lift[N][LOG]; int merge(int a,int b){ if(!a || !b) return (!a ? b : a); if(v[a][0]<v[b][0]) return a; return b; } void upd(int rt,int l,int r,int ind,int u){ if(r<ind || l>ind) return; if(l==r){ seg[rt]=merge(seg[rt],u); return; } int m=(l+r)/2; upd(rt*2,l,m,ind,u),upd(rt*2+1,m+1,r,ind,u); seg[rt]=merge(seg[rt*2],seg[rt*2+1]); } int query(int rt,int l,int r,int gl,int gr){ if(r<gl || l>gr) return 0; if(l>=gl && r<=gr) return seg[rt]; int m=(l+r)/2; return merge(query(rt*2,l,m,gl,gr),query(rt*2+1,m+1,r,gl,gr)); } void _(){ int n,q; cin >> n >> q; for(int i=1;i<=n;i++){ int l,r; cin >> l >> r; v[i]={l,r}; zip.push_back(l); zip.push_back(r); } sort(all(zip)); zip.erase(unique(all(zip)),zip.end()); for(int i=1;i<=n;i++){ v[i][0]=(lower_bound(all(zip),v[i][0])-zip.begin())+1; v[i][1]=(lower_bound(all(zip),v[i][1])-zip.begin())+1; } vector<int> events; for(int i=1;i<=n;i++) events.push_back(i); sort(all(events),[&](int a,int b){ return v[a][1]<v[b][1]; }); vector<int> ans(q+5,-1); for(int i=0;i<n;i++){ int u = events[i]; lift[u][0]=query(1,1,N,v[u][0],v[u][1]); upd(1,1,N,v[u][1],u); } for(int j=1;j<LOG;j++){ for(int i=1;i<=n;i++){ lift[i][j]=lift[lift[i][j-1]][j-1]; } } for(int j=1;j<=q;j++){ int a,b,ind=j; cin >> a >> b; if(a==b){ ans[ind]=0; continue; } if(v[a][1]>v[b][1]) continue; int res=0,p=b; for(int i=LOG-1;i>=0;i--){ if(!lift[p][i]) continue; if(v[lift[p][i]][0]>v[a][1]){ p=lift[p][i]; res+=(1LL<<i); } } //cout << "ulan: " << ind << ' ' << p << '\n'; if(lift[p][0] && v[p][0]>v[a][1]){ res++; p=lift[p][0]; } if(v[p][0]<=v[a][1]) ans[ind]=res+1; } for(int i=1;i<=q;i++){ if(ans[i]==-1) cout << "impossible\n"; else cout << ans[i] << '\n'; } } int32_t main(){ cin.tie(0); ios::sync_with_stdio(0); int tc=1;//cin >> tc; while(tc--) _(); return 0; }
#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...