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>
#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 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... |