#include <bits/stdc++.h>
using namespace std;
// ordered set whith s.order_of_key(x) method, which returns rank of element x in set s
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/
// pair printing
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "(" << par.first << "; " << par.second << ")"; return out;}
// set printing
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; }
// map printing
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for(const auto &x:cont) out << x << ", "; out << "}"; return out; }
// unordered_set printing
template <class T>
ostream& operator<<(ostream& out, const unordered_set<T> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;}
// unordered_map printing
template <class T, class U>
ostream& operator<<(ostream& out, const unordered_map<T, U> &cont) {out << "{";for(const auto &x:cont) out << x << ", ";out << "}";return out;}
// vector printing
template<class T>
ostream& operator<<(ostream& out, const vector<T> &cont){ out << "["; for (const auto &x:cont) out << x << ", "; out << "]"; return out;}
#define print(x) cout << (x) << endl;
#define dmp(x) cerr << #x << " = " << x << endl
#define dmpn(x) cerr << #x << " = " << x << "; "
#define dmpl(x) cerr << "Line " << __LINE__ << ": " << #x << " = " << x << endl
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define pb push_back
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define contains(s,x) ((s).find(x) != (s).end())
const int MOD = 998244353;
struct vertex {
int idx, start, end, parent, depth;
vector<int> children;
vector<int> binjumps;
};
int N, Q, LG = 20;
vector<vertex> g;
int eval(int x) {
if (x == INT_MAX) return INT_MAX;
return g[x].start;
}
struct SegTree {
int N;
vector<int> tree;
SegTree(vector<int> &base) {
N = 1 << (32 - __builtin_clz(sz(base)));
tree.assign(2 * N, INT_MAX);
for (int i = 0; i < sz(base); i++) tree[N + i] = base[i];
for (int i = N - 1; i > 0; i--) {
if (eval(tree[i * 2]) < eval(tree[i * 2 + 1])) tree[i] = tree[i * 2];
else tree[i] = tree[i * 2 + 1];
}
// dmp(tree);
}
int query(int l, int r, int i, int j, int idx) {
if (l <= i && j <= r) {
return tree[idx];
} else if ((i <= l && l < j) || (i < r && r <= j)) {
int mid = (i + j) / 2;
int x1 = query(l, r, i, mid, idx * 2);
int x2 = query(l, r, mid, j, idx * 2 + 1);
if (eval(x1) < eval(x2)) return x1;
else return x2;
}
return INT_MAX;
}
int bin_search_l(int base_row_idx) {
int l = N, r = N + base_row_idx;
int mn = g[tree[r]].start;
while (r - l > 0) {
int mid = (l + r) / 2;
int val = g[tree[mid]].end;
if (val < mn) {
l = mid + 1;
} else {
r = mid;
}
}
return r - N;
}
};
void dfs(int v, int p, int root, int depth) {
g[v].depth = depth;
g[v].binjumps.assign(LG, -1);
g[v].binjumps[0] = p;
for (int i = 1; i < LG; i++) {
int last = g[v].binjumps[i - 1];
if (last == -1) break;
g[v].binjumps[i] = g[last].binjumps[i - 1];
}
for (int i = 0; i < LG; i++) if (g[v].binjumps[i] == -1) g[v].binjumps[i] = root;
for (int u : g[v].children) if (u != p) {
dfs(u, v, root, depth + 1);
}
}
int relative_pos(int a, int b) {
if (g[a].start <= g[b].end && g[b].end <= g[a].end) return 0;
if (g[b].start <= g[a].end && g[a].end <= g[b].end) return 0;
if (g[a].end < g[b].end) return 1;
return -1;
}
void solve() {
cin >> N >> Q;
vector<pii> ends;
for (int i = 0; i < N; i++) {
int start, end;
cin >> start >> end;
g.pb({ i, start, end, -1 });
ends.pb({ end, i });
}
sort(all(ends));
vector<int> indices;
for (pii pr : ends) indices.pb(pr.ss);
SegTree st(indices);
for (pii pr : ends) {
int v = pr.ss;
int r = lower_bound(all(ends), pr) - ends.begin();
int l = st.bin_search_l(r);
// dmpn(v); dmpn(l); dmp(r);
if (l == r) continue;
int parent = st.query(l, r, 0, st.N, 1);
if (g[parent].start < g[v].start) {
g[v].parent = parent;
g[parent].children.pb(v);
}
}
for (int i = 0; i < N; i++) {
// if is root
if (g[i].parent == -1) dfs(i, -1, i, 0);
}
/*
for (int i = 0; i < N; i++) {
cout << i << ": ";
for (int j : g[i].children) cout << j << ", ";
cout << endl;
}
*/
while (Q--) {
int s, e;
cin >> s >> e;
s--;
e--;
// dmpn(s); dmp(e);
int v = e, ans = INT_MAX;
for (int k = LG - 1; k >= 0; k--) {
int anc = g[v].binjumps[k];
// dmpn(k); dmpn(v); dmp(anc);
int pos = relative_pos(s, anc);
if (pos == 1) {
v = anc;
} else {
int dist = g[e].depth - g[anc].depth;
if (s != anc) dist++;
// dmp(dist);
ans = min(ans, dist);
}
}
if (ans == INT_MAX) cout << "impossible" << endl;
else cout << ans << endl;
}
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
267 ms |
35720 KB |
Output is correct |
| 3 |
Correct |
273 ms |
34248 KB |
Output is correct |
| 4 |
Correct |
389 ms |
33776 KB |
Output is correct |
| 5 |
Correct |
288 ms |
34080 KB |
Output is correct |
| 6 |
Correct |
298 ms |
31944 KB |
Output is correct |
| 7 |
Incorrect |
293 ms |
32704 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
301 ms |
34352 KB |
Output is correct |
| 2 |
Correct |
356 ms |
34768 KB |
Output is correct |
| 3 |
Correct |
410 ms |
35460 KB |
Output is correct |
| 4 |
Correct |
186 ms |
24024 KB |
Output is correct |
| 5 |
Incorrect |
406 ms |
31344 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
267 ms |
35720 KB |
Output is correct |
| 3 |
Correct |
273 ms |
34248 KB |
Output is correct |
| 4 |
Correct |
389 ms |
33776 KB |
Output is correct |
| 5 |
Correct |
288 ms |
34080 KB |
Output is correct |
| 6 |
Correct |
298 ms |
31944 KB |
Output is correct |
| 7 |
Incorrect |
293 ms |
32704 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
