#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int inf = 1e15;
int n;
vector<int> dtl;
vector<vector<int>> gl;
vector<int> col;
int curco = 0;
void dfsl(int v, int p = -1, int d=0) {
dtl[v] = d;
for (auto u : gl[v]) {
if (u != p) {
dfsl(u, v, d + 1);
}
}
}
bool cmp(vector<int> a, vector<int> b) {
if (a[1] == b[1]) {
return a[0] < b[0];
}
return (a[1] < b[1]);
}
vector<vector<int>> b;
struct segtree{
int sz = 1;
vector<pair<int, int>> tree;
void init() {
while (sz < n) {
sz <<= 1;
}
tree.resize(sz * 2 - 1, {inf, inf});
build(0,0,sz);
}
void build(int v, int l, int r) {
if (r - l == 1) {
if (l < n) {
tree[v] = {b[l][0], b[l][2]};
}
return;
}
int m = (l + r) / 2;
build(v * 2 + 1, l, m);
build(v * 2 + 2, m, r);
tree[v] = min(tree[v * 2 + 1], tree[v * 2 + 2]);
}
pair<int, int> answer(int lq, int rq) {
return ans(0,0,sz,lq,rq);
}
pair<int, int> ans(int v, int l, int r, int lq, int rq) {
if (lq <= l && r <= rq) {
return tree[v];
}
if (lq >= r || rq <= l) {
return {inf, inf};
}
int m = (l + r) / 2;
auto a1 = ans(v * 2 + 1, l, m, lq, rq),
a2 = ans(v * 2 + 2, m, r, lq, rq);
return min(a1, a2);
}
};
signed main() {
int q;
cin >> n >> q;
gl.resize(n);
dtl.resize(n);
col.resize(n);
vector<vector<int>> a(n, vector<int>(3));
for (int i = 0; i < n; i++) {
cin >> a[i][0] >> a[i][1];
a[i][2] = i;
}
b = a;
auto ini = a;
sort(a.begin(), a.end());
sort(b.begin(), b.end(), cmp);
vector<int> coolle;
segtree tree;
tree.init();
vector<int> par_to_lef(n);
for (int i = 0; i < n; i++) {
par_to_lef[i] = i;
}
for (int i = n - 1; i >= 0; i--) {
int ind = b[i][2];
int beg = b[i][0];
int end = b[i][1];
int l = -1, r = n - 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (b[mid][1] >= beg) {
r = mid;
} else {
l = mid;
}
}
auto re = tree.answer(r, ind + 1);
if (re.fi < beg) {
par_to_lef[ind] = re.se;
gl[ind].push_back(re.se);
gl[re.se].push_back(ind);
} else {
coolle.push_back(ind);
}
}
curco = 0;
for (auto el : coolle) {
dfsl(el);
}
int logn = 3, vallog = 1;
while (vallog < n) {
vallog *= 2;
logn++;
}
vector<vector<int>> upstl(logn, vector<int>(n));
for (int i = 0; i < n; i++) {
upstl[0][i] = par_to_lef[i];
}
for (int j = 1; j < logn; j++) {
for (int i = 0; i < n; i++) {
upstl[j][i] = upstl[j - 1][upstl[j - 1][i]];
}
}
for (int qw = 0; qw < q; qw++) {
int s, e;
cin >> s >> e;
s--;
e--;
int curu = e;
for (int i = logn - 1; i >= 0; i--) {
if (ini[upstl[i][curu]][0] > ini[s][0])
curu = upstl[i][curu];
}
if (ini[s][1] > ini[curu][1]) {
cout << "impossible" << '\n';
} else if (s == e) {
cout << 0 << '\n';
} else {
curu = par_to_lef[curu];
if (curu == s) {
cout << dtl[e] - dtl[curu] << '\n';
} else if (ini[curu][0] <= ini[s][0]) {
cout << 1 + dtl[e] - dtl[curu] << '\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... |