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;
using ll = long long;
using ld = long double;
#define all(a) (a).begin(), (a).end()
#define sz(a) (int) a.size()
#define pb push_back
#define ff first
#define sc second
#define pii pair<int, int>
#define f(i, l, r) for (int i = (l); i < (r); i++)
#define double ld
int sp[18][18][100010];
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q; cin >> n >> q;
vector<array<int, 3>> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i][0] >> a[i][1];
a[i][2] = i;
}
sort(all(a), [](array<int, 3> x, array<int, 3> y) {
return x[1] < y[1];
});
vector<vector<int>> up(18, vector<int>(n, 0));
vector<int> nxt(n);
int prv = n - 1;
for (int i = n - 1; i >= 0; i--) {
if (i == n - 1 || a[i][1] == a[i + 1][1]) nxt[i] = prv;
else {
prv = i;
nxt[i] = prv;
}
int L = -1, R = n;
while (R - L > 1) {
int M = (L + R) / 2;
if (a[M][1] >= a[i][0]) R = M;
else L = M;
}
up[0][i] = R;
}
auto req = [&](int lvl, int l, int r) {
int lg = (int)log2(r - l + 1);
return min(sp[lvl][lg][l], sp[lvl][lg][r - (1 << lg) + 1]);
};
for (int lvl = 1; lvl < 18; lvl++) {
for (int j = 0; j < n; j++) sp[lvl - 1][0][j] = up[lvl - 1][j];
for (int i = 1; i < 18; i++) {
for (int j = 0; j + (1 << i) - 1 < n; j++) {
sp[lvl - 1][i][j] = min(sp[lvl - 1][i - 1][j], sp[lvl - 1][i - 1][j + (1 << (i - 1))]);
}
}
for (int i = 0; i < n; i++) {
up[lvl][i] = req(lvl - 1, up[lvl - 1][i], nxt[i]);
}
}
vector<int> pos(n);
for (int i = 0; i < n; i++) pos[a[i][2]] = i;
while (q--) {
int s, e; cin >> s >> e;
s--; e--;
s = pos[s];
e = pos[e];
if (a[s][1] > a[e][1]) {
cout << "impossible\n";
continue;
}
if (s == e) {
cout << "0\n";
continue;
}
int curr = e, curl = e, ans = 0;
for (int j = 17; j >= 0; j--) {
if (a[req(j, curl, curr)][1] > a[s][1]) {
ans += (1 << j);
curl = req(j, curl, curr);
curr = nxt[e];
}
}
if (ans > n) cout << "impossible\n";
else cout << ans + 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... |