This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int int64_t
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
using ar = array<int, 2>;
using ar3 = array<int, 3>;
const int64_t INF = 1ll << 60;
const int N = 2e5 + 5;
const int LG = 20;
namespace RMQ {
ar mn[LG][N];
void build(ar a[], int n) {
FOR(i, 0, n) mn[0][i] = a[i];
FOR(l, 0, LG - 1) FOR(i, 0, n)
mn[l + 1][i] = min(mn[l][i], mn[l][i + (1 << l)]);
}
int get(int l, int r) { //[l, r)
int t = __lg(r - l);
return min(mn[t][l], mn[t][r - (1 << t)])[1];
}
}
int pr[N][LG], h[N], D[2 * N], loc[N], n, q;
ar3 it[N];
ar en[2 * N];
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
FOR(i, 0, n) {
cin >> it[i][0] >> it[i][1];
it[i][2] = i;
D[i << 1] = it[i][0];
D[i << 1 | 1] = it[i][1];
}
fill(en, en + 2 * n, ar{INF, INF});
sort(D, D + 2 * n);
sort(it, it + n, [](const auto &A, const auto &B) {
if (A[0] != B[0]) return A[0] < B[0];
return A[2] < B[2];
});
FOR(i, 0, n) {
it[i][0] = lower_bound(D, D + 2 * n, it[i][0]) - D;
it[i][1] = lower_bound(D, D + 2 * n, it[i][1]) - D;
en[it[i][1]] = min(en[it[i][1]], ar{it[i][0], i});
loc[it[i][2]] = i;
}
RMQ::build(en, 2 * n);
FOR(i, 0, n) {
pr[i][0] = i;
auto [l, r, x] = it[i];
int idx = RMQ::get(l, r + 1);
assert(idx <= i);
if (idx != i) {
h[i] = h[idx] + 1;
pr[i][0] = idx;
FOR(l, 0, LG - 1)
pr[i][l + 1] = pr[pr[i][l]][l];
}
}
while (q--) {
int s, e;
cin >> s >> e;
--s, --e;
s = loc[s], e = loc[e];
if (it[e][1] < it[s][0] || it[s][1] > it[e][1]) cout << "impossible\n";
else if (s == e) cout << 0 << '\n';
else if (it[s][1] < it[e][0]) {
int sr = it[s][1], v = e;
for (int i = LG - 1; i >= 0; --i) {
int l = it[pr[v][i]][0];
if (l > sr)
v = pr[v][i];
}
v = pr[v][0];
if (it[v][0] > sr) cout << "impossible\n";
else cout << h[e] - h[v] + 1 << '\n';
}
}
return 0;
}
# | 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... |