#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=1e5+9;
pii a[maxn];
int st[maxn][19];
int n,q;
pii st1[maxn*8];
pii combine(const pii &p1, const pii &q1){
if (p1.fi>q1.fi)return q1;
return p1;
}
void build(int id,int l,int r){
st1[id]={maxn*2,0};
if (l==r)return;
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
}
void update(int id,int l,int r,int u,pii val){
if (l>u||r<u)return;
if (l==r){
st1[id]=combine(st1[id],val);
return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,val);
update(id*2+1,mid+1,r,u,val);
st1[id]=combine(st1[id*2],st1[id*2+1]);
}
pii get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return {maxn*2,0};
if (u<=l&&r<=v)return st1[id];
int mid=(l+r)/2;
return combine(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
void build(){
int m=n*2;
build(1,1,m);
for1(i,1,n){
update(1,1,m,a[i].se,{a[i].fi,i});
}
for1(i,1,n){
pii tmp=get(1,1,m,a[i].fi,a[i].se);
//if (i==64571)cout<<tmp.fi<<" "<<a[i].fi<<'\n';
if (tmp.fi>=a[i].fi)continue;
st[i][0]=tmp.se;
}
for1(j,1,18){
for1(i,1,n){
st[i][j]=st[st[i][j-1]][j-1];
}
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("events.INP","r",stdin);
//freopen("events.OUT","w",stdout);
cin>>n>>q;
vector<int>nen;
nen.pb(0);
for1(i,1,n){
cin>>a[i].fi>>a[i].se;
nen.pb(a[i].fi);
nen.pb(a[i].se);
}
sort(all(nen));
map<int,int>n1;
for1(i,1,sz(nen)-1){
if (nen[i]==nen[i-1])continue;
n1[nen[i]]=n1[nen[i-1]]+1;
}
for1(i,1,n){
a[i].fi=n1[a[i].fi];
a[i].se=n1[a[i].se];
//cout<<"type "<<" "<<a[i].fi<<" "<<a[i].se<<'\n';
}
build();
for1(i,1,q){
int s,e;
cin>>s>>e;
//if (i!=13)continue;
if (a[s].se>a[e].se){
cout<<"impossible"<<'\n';
}
else if (s==e){
cout<<0<<'\n';
}
else if (a[e].fi<=a[s].se&&a[s].se<=a[e].se){
cout<<1<<'\n';
}
else {
int ans=0;
for2(j,18,0){
if (!st[e][j])continue;
int id=st[e][j];
if (a[id].fi>a[s].se){
//cerr<<j<<'\n';
e=id;
ans+=(1<<j);
}
}
//cerr<<st[e][0]<<'\n';
//cout<<e<<'\n';
//cout<<a[s].fi<<" "<<a[s].se<<'\n';
//cout<<get(1,1,2*n,a[e].fi,a[e].se).fi<<" "<<a[e].fi<<'\n';
if (st[e][0]==0)ans=-1;
else {
int id=st[e][0];
if (a[id].fi<=a[s].se){
ans+=2;
}
else ans=-1;
}
if (ans==-1)cout<<"impossible"<<'\n';
else cout<<ans<<'\n';
}
}
}
Compilation message
interface.cpp: In function 'int publish(std::vector<int>)':
interface.cpp:20:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
20 | if(v.size() != N) {
| ~~~~~~~~~^~~~
interface.cpp: In function 'void answer(std::vector<int>)':
interface.cpp:36:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
36 | if(v.size() != N) {
| ~~~~~~~~~^~~~
/usr/bin/ld: /tmp/ccKx0Jyd.o: in function `main':
interface.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cck6DUQd.o:art.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccKx0Jyd.o: in function `main':
interface.cpp:(.text.startup+0x16): undefined reference to `solve(int)'
collect2: error: ld returned 1 exit status
