#include <bits/stdc++.h>
using namespace std;
const int nx=1e5+5, kx=17, inf=1e9;
struct segtree
{
struct node
{
pair<int, int> mn;
node *l, *r;
node(pair<int, int> mn=make_pair(2e9, 0)): mn(mn), l(0), r(0) {}
};
typedef node* pnode;
pnode rt;
void update(int l, int r, pnode &k, int idx, pair<int, int> vl)
{
if (!k) k=new node();
if (idx<l||r<idx) return;
//cout<<"debug "<<l<<' '<<r<<'\n';
if (l==r) return k->mn=min(k->mn, vl), void();
int md=(l+r)/2;
update(l, md, k->l, idx, vl);
update(md+1, r, k->r, idx, vl);
k->mn=min(k->l->mn, k->r->mn);
}
pair<int, int> query(int l, int r, pnode k, int ql, int qr)
{
if (qr<l||r<ql||!k) return {2e9, 0};
if (ql<=l&&r<=qr) return k->mn;
int md=(l+r)/2;
return min(query(l, md, k->l, ql, qr), query(md+1, r, k->r, ql, qr));
}
} d;
struct range
{
int l, r, idx;
range(int l, int r, int idx): l(l), r(r), idx(idx){}
bool operator< (const range &o) const
{
if (r==o.r) return l<o.l;
return r<o.r;
}
};
vector<range> v;
int n, q, s[nx], e[nx], a, b, idx[nx], pa[nx][kx];
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>q;
for (int i=0; i<n; i++) cin>>s[i]>>e[i], v.push_back({s[i], e[i], i});
sort(v.begin(), v.end());
for (int i=0; i<n; i++) idx[v[i].idx]=i;
for (int i=0; i<n; i++) d.update(1, inf, d.rt, v[i].r, {v[i].l, i});
for (int i=0; i<n; i++) pa[i][0]=d.query(1, inf, d.rt, v[i].l, v[i].r).second;
for (int i=1; i<kx; i++) for (int j=0; j<n; j++) pa[j][i]=pa[pa[j][i-1]][i-1];
while (q--)
{
cin>>a>>b;
a=idx[a-1], b=idx[b-1];
if (b<a) cout<<"impossible\n";
else if (b==a) cout<<"0\n";
else if (v[a].r==v[b].r) cout<<"1\n";
else
{
int res=0;
for (int i=kx-1; i>=0; i--) if (pa[b][i]>a) b=pa[b][i], res+=(1<<i);
res++;
b=pa[b][0];
if (v[b].l<=v[a].r&&v[a].r<=v[b].r) cout<<res<<'\n';
else cout<<"impossible\n";
}
}
}
# | 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... |