/**
* author : pham van sam
* created : 25 October 2023 (Wednesday)
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define clog if(false) cerr
#endif
template < class T, T (*f) (T, T), T (*e) ()>
struct segment_tree {
vector <T> it;
int n;
void update(int u, T p) {
u += n - 1;
it[u] = f(it[u], p);
for(; u >>= 1; ) {
it[u] = f(it[u << 1], it[u << 1 | 1]);
}
}
void set(int u, T p) {
u--;
for (it[u += n] = p; u >>= 1; ) {
it[u] = f(it[u << 1], it[u << 1 | 1]);
}
}
T get(int p) {
return it[p += n - 1];
}
T get(int l, int r) {
l--;
T resl = e(), resr = e();
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if(l & 1) resl = f(resl, it[l++]);
if(r & 1) resr = f(it[--r], resr);
}
return f(resl, resr);
}
segment_tree(int n = 0) : n(n), it(n << 1 | 1) {
fill(it.begin(), it.end(), T{});
}
};
pair <int, int> op(pair <int, int> a, pair <int, int> b) {
if(a.first == 0) return b;
if(b.first == 0) return a;
return min(a, b);
};
pair <int, int> e() {
return make_pair(0, 0);
};
const int MAXN = 1e5 + 5;
const int LOG = 20;
struct segment {
int l, r, ind;
friend ostream & operator << (ostream &out, const segment &a) {
return out << "(" << a.l << ", " << a.r << ", " << a.ind << ")";
}
} A[MAXN];
int n, q, anc[MAXN][LOG], pos[MAXN];
void you_make_it(void) {
cin >> n >> q;
vector <int> compress;
for (int i = 1; i <= n; ++i) {
cin >> A[i].l >> A[i].r;
A[i].ind = i;
compress.push_back(A[i].l);
compress.push_back(A[i].r);
}
sort(compress.begin(), compress.end());
compress.erase(unique(compress.begin(), compress.end()), compress.end());
for (int i = 1; i <= n; ++i) {
A[i].l = lower_bound(compress.begin(), compress.end(), A[i].l) - compress.begin() + 1;
A[i].r = lower_bound(compress.begin(), compress.end(), A[i].r) - compress.begin() + 1;
}
sort(A + 1, A + n + 1, [&] (const segment &a, const segment &b) -> bool {
return make_pair(a.l, a.r) < make_pair(b.l, b.r);
});
for (int i = 1; i <= n; ++i) clog << debug(A[i]) << '\n';
segment_tree <pair <int, int>, op, e> it((int) compress.size());
for (int i = 1; i <= n; ++i) {
pos[A[i].ind] = i;
it.update(A[i].r, make_pair(A[i].l, i));
auto [_, id] = it.get(A[i].l, A[i].r);
anc[i][0] = id;
clog << anc[i][0] << " \n"[i == 1];
}
for (int i = 1; i < LOG; ++i) {
for (int u = 1; u <= n; ++u) {
anc[u][i] = anc[anc[u][i - 1]][i - 1];
}
}
while(q--) {
int u, v; cin >> u >> v;
u = pos[u], v = pos[v];
if(u == v) {
cout << "0\n";
continue;
}
if(u > v) {
cout << "impossible\n";
continue;
}
if(A[u].r == A[v].r) {
cout << "1\n";
continue;
}
int ans = 0;
for (int i = LOG - 1; i >= 0; --i) {
if(A[u].r < A[anc[v][i]].l) {
ans += 1 << i;
v = anc[v][i];
}
}
if(A[v].l <= A[u].r && A[u].r <= A[v].r) ans++;
else {
v = anc[v][0];
ans += 2;
}
if(A[v].l <= A[u].r && A[u].r <= A[v].r) cout << ans;
else cout << "impossible";
cout << '\n';
clog << u << " " << v << '\n';
}
}
signed main() {
#ifdef LOCAL
freopen("TASK.inp", "r", stdin);
freopen("TASK.out", "w", stdout);
#endif
auto start_time = chrono::steady_clock::now();
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
you_make_it();
auto end_time = chrono::steady_clock::now();
cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;
return (0 ^ 0);
}
// Dream it. Wish it. Do it.
Compilation message
events.cpp: In function 'void you_make_it()':
events.cpp:99:42: error: 'debug' was not declared in this scope
99 | for (int i = 1; i <= n; ++i) clog << debug(A[i]) << '\n';
| ^~~~~
events.cpp: In instantiation of 'segment_tree<T, f, e>::segment_tree(int) [with T = std::pair<int, int>; T (* f)(T, T) = op; T (* e)() = e]':
events.cpp:101:67: required from here
events.cpp:19:9: warning: 'segment_tree<std::pair<int, int>, op, e>::n' will be initialized after [-Wreorder]
19 | int n;
| ^
events.cpp:18:16: warning: 'std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > segment_tree<std::pair<int, int>, op, e>::it' [-Wreorder]
18 | vector <T> it;
| ^~
events.cpp:50:5: warning: when initialized here [-Wreorder]
50 | segment_tree(int n = 0) : n(n), it(n << 1 | 1) {
| ^~~~~~~~~~~~
