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 <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
const int ln=18;
int pow2[ln];
const int N=100000;
int st[N];
int en[N];
pair<int,int> seg[4*N];
void Build(int l,int r,int pos){
if(l==r){
seg[pos]=mp(st[l],l);
return;
}
int mid=(l+r)/2;
Build(l,mid,2*pos);
Build(mid+1,r,2*pos+1);
seg[pos]=min(seg[2*pos],seg[2*pos+1]);
}
pair<int,int> Query(int l,int r,int pos,int ql,int qr){
if(ql>r || qr<l) return mp(1000000001,-1);
if(ql<=l && qr>=r) return seg[pos];
int mid=(l+r)/2;
return min(Query(l,mid,2*pos,ql,qr),Query(mid+1,r,2*pos+1,ql,qr));
}
void solve(){
int n,q;
cin >> n >> q;
vector<pair<pair<int,int>,int>> v;
for(int i=0;i<n;i++){
int s,e;
cin >> s >> e;
v.push_back(mp(mp(e,s),i));
}
sort(v.begin(),v.end());
int rn[n];
for(int i=0;i<n;i++) rn[v[i].second]=i;
for(int i=0;i<n;i++){
st[i]=v[i].first.second;
en[i]=v[i].first.first;
}
int sparsetable[ln][n];
Build(0,n-1,1);
for(int i=0;i<n;i++){
int si=lower_bound(en,en+n,st[i])-en;
int ei=upper_bound(en,en+n,en[i])-en-1;
int ind=si;
for(int j=si;j<=ei;j++){
if(st[j]<st[ind]) ind=j;
}
sparsetable[0][i]=ind;//Query(0,n-1,1,si,ei).second;
}
for(int k=0;k<ln-1;k++){
for(int i=0;i<n;i++){
sparsetable[k+1][i]=sparsetable[k][sparsetable[k][i]];
}
}
while(q--){
int u,v;
cin >> u >> v;
u--,v--;
u=rn[u];
v=rn[v];
if(en[v]<en[u]){
cout << "impossible" << "\n";
return;
}
if(u==v){
cout << 0 << "\n";
continue;
}
if(st[v]<=en[u]){
cout << 1 << "\n";
continue;
}
int ans=0;
for(int k=ln-1;k>=0;k--){
if(st[sparsetable[k][v]]>en[u]){
ans+=pow2[k];
v=sparsetable[k][v];
}
}
if(st[sparsetable[0][v]]<=en[u]){
cout << ans+2 << "\n";
continue;
}
/*int ans=1;
while(v!=sparsetable[0][v]){
v=sparsetable[0][v];
ans++;
if(st[v]<=en[u]) break;
}
if(st[v]<=en[u]) cout << ans << "\n";
else*/ cout << "impossible" << "\n";
}
}
int main(){
pow2[0]=1;
for(int i=0;i<ln-1;i++){
pow2[i+1]=2*pow2[i];
}
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
//cin >> t;
t=1;
while(t--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |