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;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
int m;
cin >> m;
vector<vector<vector<int>>> qs(n, vector<vector<int>>(2));
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
--a; --b;
if (a < b) {
qs[a][0].push_back(b);
qs[min(b, a + k - 1)][0].push_back(~b);
} else {
qs[max(b, a - k + 1)][1].push_back(b);
qs[a][1].push_back(~b);
}
}
const int LOG = 20;
vector<vector<int>> R(n, vector<int>(LOG));
vector<vector<int>> L(n, vector<int>(LOG));
vector<multiset<int>> st(2);
for (int i = 0; i < n; i++) {
for (int t = 0; t < 2; t++) {
for (int x : qs[i][t]) {
if (x >= 0) {
st[t].insert(x);
}
}
}
R[i][0] = (st[0].empty() ? i : *prev(st[0].end()));
L[i][0] = (st[1].empty() ? i : *st[1].begin());
for (int t = 0; t < 2; t++) {
for (int x : qs[i][t]) {
if (x < 0) {
x = ~x;
st[t].erase(st[t].find(x));
}
}
}
}
for (int j = 1; j < LOG; j++) {
vector<vector<int>> mn(n, vector<int>(LOG));
vector<vector<int>> mx(n, vector<int>(LOG));
vector<int> logs(n + 1);
for (int i = 0; i < n; i++) {
mn[i][0] = L[i][j - 1];
mx[i][0] = R[i][j - 1];
}
for (int l = 1; l < LOG; l++) {
for (int i = 0; i + (1 << l) <= n; i++) {
mn[i][l] = min(mn[i][l - 1], mn[i + (1 << (l - 1))][l - 1]);
mx[i][l] = max(mx[i][l - 1], mx[i + (1 << (l - 1))][l - 1]);
}
}
for (int i = 2; i <= n; i++) {
logs[i] = logs[i >> 1] + 1;
}
auto QueryMin = [&](int l, int r) {
int k = logs[r - l + 1];
return min(mn[l][k], mn[r - (1 << k) + 1][k]);
};
auto QueryMax = [&](int l, int r) {
int k = logs[r - l + 1];
return max(mx[l][k], mx[r - (1 << k) + 1][k]);
};
for (int i = 0; i < n; i++) {
L[i][j] = QueryMin(L[i][j - 1], R[i][j - 1]);
R[i][j] = QueryMax(L[i][j - 1], R[i][j - 1]);
}
}
vector<vector<vector<int>>> mn(LOG, vector<vector<int>>(n, vector<int>(LOG)));
vector<vector<vector<int>>> mx(LOG, vector<vector<int>>(n, vector<int>(LOG)));
vector<int> logs(n + 1);
for (int i = 2; i <= n; i++) {
logs[i] = logs[i >> 1] + 1;
}
for (int l = 0; l < LOG; l++) {
for (int i = 0; i < n; i++) {
mn[l][i][0] = L[i][l];
mx[l][i][0] = R[i][l];
}
for (int j = 1; j < LOG; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
mn[l][i][j] = min(mn[l][i][j - 1], mn[l][i + (1 << (j - 1))][j - 1]);
mx[l][i][j] = max(mx[l][i][j - 1], mx[l][i + (1 << (j - 1))][j - 1]);
}
}
}
auto QueryMin = [&](int i, int l, int r) {
int k = logs[r - l + 1];
return min(mn[i][l][k], mn[i][r - (1 << k) + 1][k]);
};
auto QueryMax = [&](int i, int l, int r) {
int k = logs[r - l + 1];
return max(mx[i][l][k], mx[i][r - (1 << k) + 1][k]);
};
int q;
cin >> q;
while (q--) {
int a, b;
cin >> a >> b;
--a; --b;
if (L[a][LOG - 1] > b || R[a][LOG - 1] < b) {
cout << -1 << '\n';
continue;
}
int cl = a, cr = a;
int res = 1;
for (int i = LOG - 1; i >= 0; i--) {
if (QueryMin(i, cl, cr) <= b && QueryMax(i, cl, cr) >= b) {
continue;
}
res += (1 << i);
int new_cl = QueryMin(i, cl, cr);
int new_cr = QueryMax(i, cl, cr);
cl = new_cl;
cr = new_cr;
}
cout << res << '\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... |