#include <bits/stdc++.h>
#define maxn 100005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
int n, q;
int f[20][maxn];
ii a[maxn];
int c[2*maxn], n1 = 0;
ii lz[8*maxn], st[8*maxn];
void apply(int r, ii d) {
lz[r] = max(lz[r], d);
st[r] = max(st[r], d);
}
void down(int r) {
apply(r<<1, lz[r]);
apply(r<<1|1, lz[r]);
}
void up(int r) {
st[r] = max(st[r<<1], st[r<<1|1]);
}
void update(int u, int v, ii d, int r = 1, int lo = 1, int hi = n1) {
if (u <= lo && hi <= v) {
apply(r, d);
return;
}
down(r);
int mid = (lo + hi) >> 1;
if (u <= mid) update(u, v, d, r<<1, lo, mid);
if (v > mid) update(u, v, d, r<<1|1, mid+1, hi);
up(r);
}
ii get(int u, int v, int r = 1, int lo = 1, int hi = n1) {
if (u <= lo && hi <= v) return st[r];
int mid = (lo + hi) >> 1;
down(r);
return max(u <= mid ? get(u, v, r<<1, lo, mid) : ii{0, 0}, v > mid ? get(u, v, r<<1|1, mid+1, hi) : ii{0, 0});
}
int it[48*maxn], L[48*maxn], R[48*maxn], nt = 0;
int root[2*maxn];
vector<ii> adj[2*maxn];
int build(int lo = 1, int hi = n1) {
if (lo == hi) return ++nt;
int cur = ++nt, mid = (lo + hi) >> 1;
L[cur] = build(lo, mid);
R[cur] = build(mid+1, hi);
return cur;
}
int updPst(int u, int d, int oldver, int lo = 1, int hi = n1) {
if (lo == hi) {
it[++nt] = it[oldver] + d;
return nt;
}
int cur = ++nt, mid = (lo + hi) >> 1;
if (u <= mid) {
L[cur] = updPst(u, d, L[oldver], lo, mid);
R[cur] = R[oldver];
} else {
L[cur] = L[oldver];
R[cur] = updPst(u, d, R[oldver], mid+1, hi);
}
it[cur] = it[L[cur]] + it[R[cur]];
return cur;
}
int getPst(int u, int v, int r, int lo = 1, int hi = n1) {
if (u <= lo && hi <= v) return it[r];
int mid = (lo + hi) >> 1;
return (u <= mid ? getPst(u, v, L[r], lo, mid) : 0) +
(v > mid ? getPst(u, v, R[r], mid+1, hi) : 0);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;
for (int i = 1; i <= n; i++) {
c[++n1] = a[i].fi;
c[++n1] = a[i].se;
}
sort(c + 1, c + n1 + 1);
n1 = unique(c + 1, c + n1 + 1) - c - 1;
root[0] = build();
for (int i = 1; i <= n; i++) {
int p = lower_bound(c + 1, c + n1 + 1, a[i].fi) - c,
q = lower_bound(c + 1, c + n1 + 1, a[i].se) - c;
adj[p].emplace_back(q, 1);
adj[q+1].emplace_back(q, -1);
update(p, q, ii{a[i].se, i});
}
for (int i = 1; i <= n1; i++) {
root[i] = root[i-1];
for (auto [v, p] : adj[i]) root[i] = updPst(v, p, root[i]);
}
for (int i = 1; i <= n; i++) {
int p = lower_bound(c + 1, c + n1 + 1, a[i].fi) - c,
q = lower_bound(c + 1, c + n1 + 1, a[i].se) - c;
ii o = get(p, q);
if (o.fi == a[i].se) f[0][i] = i;
else f[0][i] = o.se;
}
for (int i = 1; i < 20; i++) for (int j = 1; j <= n; j++) f[i][j] = f[i-1][f[i-1][j]];
while (q--) {
int s, e;
cin >> s >> e;
if (s == e) {
cout << "0\n";
continue;
}
if (a[s].se > a[e].se) {
cout << "impossible\n";
continue;
}
auto [u, v] = a[e];
int ans = 0;
for (int i = 19; i >= 0; i--)
if (a[f[i][s]].se < u) {
ans += (1<<i);
s = f[i][s];
}
if (u <= a[s].se && a[s].se <= v) {
cout << ++ans << "\n";
continue;
}
int p = lower_bound(c + 1, c + n1 + 1, a[s].se) - c;
int A = lower_bound(c + 1, c + n1 + 1, u) - c,
B = lower_bound(c + 1, c + n1 + 1, v) - c;
if (getPst(A, B, root[p])) cout << (ans += 2) << "\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... |