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>
using namespace std;
const int maxn = 100010, SZ = 1300;
int n, q, b[maxn], rmq[17][maxn], bel[maxn], bl[maxn], br[maxn];
int num[maxn / SZ + 5][SZ + 5], tmp[maxn], sz[maxn], rb[maxn];
short pos[maxn][SZ + 5], tr[maxn][SZ + 5];
array<int, 2> a[maxn];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> q;
vector<int> V;
for (int i = 1; i <= n; i++) {
cin >> a[i][0] >> a[i][1], V.push_back(a[i][1]);
}
sort(V.begin(), V.end());
V.resize(unique(V.begin(), V.end()) - V.begin());
fill(b + 1, b + n + 1, n + 1);
for (int i = 1; i <= n; i++) {
a[i][0] = lower_bound(V.begin(), V.end(), a[i][0]) - V.begin() + 1;
a[i][1] = lower_bound(V.begin(), V.end(), a[i][1]) - V.begin() + 1;
b[a[i][1]] = min(b[a[i][1]], a[i][0]);
}
for (int i = 1; i <= n; i++) {
br[bel[i] = (i - 1) / SZ + 1] = i;
if (!bl[bel[i]]) bl[bel[i]] = i;
}
copy(b + 1, b + n + 1, rmq[0] + 1);
for (int k = 1; k < 17; k++) {
memcpy(rmq[k], rmq[k - 1], sizeof(rmq[k]));
for (int i = (1 << (k - 1)) + 1; i <= n; i++) {
rmq[k][i] = min(rmq[k][i], rmq[k - 1][i - (1 << (k - 1))]);
}
}
auto qmin = [&](int l, int r) {
int k = __lg(r - l + 1);
return min(rmq[k][l + (1 << k) - 1], rmq[k][r]);
};
auto go = [&](int s, int r) {
r = min(r, rb[s]);
if (b[r] <= s) return r;
for (int i = __lg(r - s + 1); ~i && r > s; i--) {
if (rmq[i][r] > s) r -= 1 << i;
}
return r <= s ? 0 : r;
};
for (int i = 1; i <= n; i++) {
rb[i] = n, rb[i] = go(i, n);
}
for (int k = 1; k <= bel[n]; k++) {
for (int i = br[k], j = br[k]; i >= bl[k]; i--) {
for (; j >= max(bl[k], b[i]); j--) num[k][j - bl[k]] = j < i ? i : 0;
}
}
for (int i = 1; i <= n; i++) {
int k = bel[i], L = bl[k], R = br[k];
for (int j = num[k][i - L]; j && j <= R; j = num[k][j - L]) {
tr[i][sz[i]++] = j - L;
}
for (int j = 0, k = 0; j <= R - L; j++) {
while (k < sz[i] && tr[i][k] < j) k++;
pos[i][j] = k;
}
}
while (q--) {
int s, t, ans = 0;
cin >> s >> t;
if (s == t) { cout << "0\n"; continue; }
for (s = a[s][1]; s && s < a[t][0]; ans++) {
if (bel[s] == bel[a[t][0]]) {
for (int i = a[t][0], j = a[t][0]; i >= s; i--) {
int v = max(s, i == a[t][0] ? qmin(i, a[t][1]) : b[i]);
for (; j >= v; j--) tmp[j] = j < i ? i : 0;
}
for (; s && s < a[t][0]; ans++) s = tmp[s];
break;
}
int nxt = qmin(bl[bel[s] + 1], a[t][1]);
if (nxt <= s) {
s = go(s, a[t][1]);
} else {
if (!sz[s] || nxt - bl[bel[s]] > tr[s][sz[s] - 1]) { s = 0; break; }
int i = pos[s][nxt - bl[bel[s]]];
ans += i, s = bl[bel[s]] + tr[s][i];
if (s < a[t][0]) s = go(s, a[t][1]), ans++;
}
}
if (a[t][0] <= s && s <= a[t][1]) cout << ans + 1 << "\n";
else cout << "impossible\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... |