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<vector>
#include<algorithm>
#include<utility>
using namespace std;
struct event{
int start,end,pos;
};
bool cmp(event a,event b){
if(a.end==b.end) return a.start<b.start;
return a.end<b.end;
}
struct st{
vector<pair<int,int> > seg;
st(vector<int> &vec,int n){
seg.resize(4*n+4);
build(1,n,1,vec);
}
void build(int l,int r,int ind,vector<int> &vec){
if(l==r){
if(vec[l-1]==-1) seg[ind]=make_pair(1e9+1,l-1);
else seg[ind]=make_pair(vec[l-1],l-1);
return;
}
int mid=(l+r)>>1;
build(l,mid,ind*2,vec);
build(mid+1,r,ind*2+1,vec);
seg[ind]=min(seg[ind*2],seg[ind*2+1]);
}
pair<int,int> query(int l,int r,int start,int end,int ind){
if(r<start||end<l) return make_pair(1e9+1,1e9+1);
if(start<=l&&r<=end) return seg[ind];
int mid=(l+r)>>1;
return min(query(l,mid,start,end,ind*2),query(mid+1,r,start,end,ind*2+1));
}};
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n,q;
cin>>n>>q;
vector<event> vec(n);
int a,b;
for(int i=0;i<n;i++){
cin>>a>>b;
vec[i].start=a;
vec[i].end=b;
vec[i].pos=i;
}
vector<int> ori(n+1);
sort(vec.begin(),vec.end(),cmp);
for(int i=0;i<n;i++) ori[vec[i].pos+1]=i;
vector<vector<int> > anc(17,vector<int>(n));
anc[0][0]=-1;
//for(int i=0;i<n;i++) cout<<"\n"<<vec[i].start<<" "<<vec[i].end;
for(int i=1;i<n;i++){
if(vec[i-1].end<vec[i].start){
anc[0][i]=-1;
continue;
}
int l=0,r=i-1;
while(l<r){
int mid=(l+r)>>1;
if(vec[mid].end<vec[i].start){
l=mid+1;
}
else{
r=mid;
}
}
anc[0][i]=l;
}
vector<int> bruv(n);
for(int i=0;i<n;i++) bruv[i]=vec[i].start;
st omg(bruv,n);
for(int i=1;i<17;i++){
for(int j=0;j<n;j++){
if(anc[i-1][j]==-1) {
anc[i][j]=-1;
continue;
}
int tmp=omg.query(1,n,anc[i-1][j]+1,j+1,1).second;
if(tmp==1e9+1) anc[i][j]=-1;
else anc[i][j]=anc[i-1][tmp];
}
}
/*for(int i=0;i<17;i++){
for(int j=0;j<n;j++){
cout<<anc[i][j]<<" ";
}
cout<<"\n";
}*/
for(int i=0;i<q;i++){
cin>>a>>b;
if(a==b){
cout<<"0\n";
continue;
}
a=ori[a],b=ori[b];
if(vec[a].end==vec[b].end){
cout<<"1\n";
continue;
}
if(a>b){
cout<<"impossible\n";
continue;
}
int ans=0;
for(int j=16;j>=0;j--){
if(anc[j][b]>a&&anc[j][b]!=-1) b=omg.query(1,n,anc[j][b]+1,b+1,1).second,ans+=(1<<j);
}
if(anc[0][b]<=a&&anc[0][b]!=-1){
cout<<ans+1<<"\n";
}
else cout<<"impossible\n";
}
}
/*1 3
2 4
3 7
4 7
7 9*/
# | 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... |