This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 1e5 + 5, INF = 1e9, MAX_Q = 1e5 + 5;
int n, q;
array<int, MAX_N> l, r;
int n_ccs;
unordered_map<int, int> cc;
array<pii, 8 * MAX_N> st; // {r[i], i}
void update(int l, int r, pii x, int u = 1, int lo = 1, int hi = n_ccs) {
if (l <= lo && hi <= r) { st[u] = max(st[u], x); return; }
int mid = (lo + hi) / 2;
if (l <= mid) update(l, r, x, 2 * u, lo, mid);
if (r > mid) update(l, r, x, 2 * u + 1, mid + 1, hi);
}
pii query(int i, int u = 1, int lo = 1, int hi = n_ccs) {
if (lo == hi) return st[u];
int mid = (lo + hi) / 2;
if (i <= mid) return max(st[u], query(i, 2 * u, lo, mid));
else return max(st[u], query(i, 2 * u + 1, mid + 1, hi));
}
array<array<int, 20>, MAX_N> anc;
void precomp() {
set<int> coords;
for (int i = 1; i <= n; i++) coords.insert(l[i]), coords.insert(r[i]);
while (coords.size()) {
n_ccs++, cc[*coords.begin()] = n_ccs;
coords.erase(coords.begin());
}
for (int i = 1; i <= n; i++) update(cc[l[i]], cc[r[i]], {r[i], i});
for (int i = 1; i <= n; i++) {
pii x = query(cc[r[i]]);
if (x == make_pair(r[i], i)) continue;
anc[i][0] = x.second;
// cout << i << ": " << x.second << endl;
}
for (int i = 1; i < 20; i++)
for (int j = 1; j <= n; j++)
anc[j][i] = anc[anc[j][i - 1]][i - 1];
}
int main() {
// freopen("event.in", "r", stdin);
cin.sync_with_stdio(false), cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];
precomp();
for (int i = 1; i <= q; i++) {
int s, f; cin >> s >> f;
if (s == f) { cout << 0 << '\n'; continue; }
if (r[s] > r[f]) { cout << "impossible" << '\n'; continue; }
int j = i, ans = 0;
for (int k = 19; k >= 0; k--)
if (anc[j][k] != 0 && r[anc[j][k]] < r[f])
j = anc[j][k], ans += (1 << k);
j = anc[j][0], ans++;
if (j == 0) { cout << "impossible" << '\n'; continue; }
assert(r[j] >= r[f]);
cout << ans << '\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... |