#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = double;
const int LOG = 21;
const int MAXM = 1e5;
int lift[MAXM + 1][LOG + 2];
struct RMQ {
vector<int> tree;
int n;
void init(int n, int val) {
this->n = n;
tree = vector<int>(4 * n, val);
}
void update_max(int i, int l, int r, int qp, int val) {
if (l == r) {
tree[i] = max(tree[i], val);
return;
}
int m = (l + r) / 2;
if (qp <= m) update_max(i * 2, l, m, qp, val);
else update_max(i * 2 + 1, m + 1, r, qp, val);
tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}
void update_max(int qp, int val) {
update_max(1, 1, n, qp, val);
}
void update_min(int i, int l, int r, int qp, int val) {
if (l == r) {
tree[i] = min(tree[i], val);
return;
}
int m = (l + r) / 2;
if (qp <= m) update_min(i * 2, l, m, qp, val);
else update_min(i * 2 + 1, m + 1, r, qp, val);
tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
}
void update_min(int qp, int val) {
update_min(1, 1, n, qp, val);
}
int query_max(int i, int l, int r, int ql, int qr) {
if (l > qr || r < ql) return -1;
if (ql <= l && r <= qr) return tree[i];
int m = (l + r) / 2;
return max(query_max(i * 2, l, m, ql, qr), query_max(i * 2 + 1, m + 1, r, ql, qr));
}
int query_max(int ql, int qr) {
return query_max(1, 1, n, ql, qr);
}
int query_min(int i, int l, int r, int ql, int qr) {
if (l > qr || r < ql) return n + 1;
if (ql <= l && r <= qr) return tree[i];
int m = (l + r) / 2;
return min(query_min(i * 2, l, m, ql, qr), query_min(i * 2 + 1, m + 1, r, ql, qr));
}
int query_min(int ql, int qr) {
return query_min(1, 1, n, ql, qr);
}
void setval(int i, int l, int r, int qp, int val) {
if (l == r) {
tree[i] = val;
return;
}
int m = (l + r) / 2;
if (qp <= m) setval(i * 2, l, m, qp, val);
else setval(i * 2 + 1, m + 1, r, qp, val);
tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
}
void setval(int qp, int val) {
setval(1, 1, n, qp, val);
}
};
struct RMQ_MIN {
vector<int> tree;
int n;
void init(int n, int val) {
this->n = n;
tree = vector<int>(4 * n, val);
}
void update_min(int i, int l, int r, int qp, int val) {
if (l == r) {
tree[i] = min(tree[i], val);
return;
}
int m = (l + r) / 2;
if (qp <= m) update_min(i * 2, l, m, qp, val);
else update_min(i * 2 + 1, m + 1, r, qp, val);
tree[i] = min(tree[i * 2], tree[i * 2 + 1]);
}
void update_min(int qp, int val) {
update_min(1, 1, n, qp, val);
}
int query_min(int i, int l, int r, int ql, int qr) {
if (l > qr || r < ql) return n + 1;
if (ql <= l && r <= qr) return tree[i];
int m = (l + r) / 2;
return min(query_min(i * 2, l, m, ql, qr), query_min(i * 2 + 1, m + 1, r, ql, qr));
}
int query_min(int ql, int qr) {
return query_min(1, 1, n, ql, qr);
}
};
int main() {
//~ ofstream cout("out.txt");
ios::sync_with_stdio(0);
cin.tie(0);
int n, k, m;
cin >> n >> k >> m;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= LOG; ++j) {
lift[i][j] = -1;
}
}
vector<vector<array<int, 2>>> events(n + 1), revents(n + 1);
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
if (a < b) {
int till = min(b, a + k);
events[a].push_back({b, till});
events[till].push_back({-b, till});
} else {
a = n - a + 1;
b = n - b + 1;
int till = min(b, a + k);
assert(a < till);
assert(a > 0);
assert(b <= n);
revents[a].push_back({b, till});
revents[till].push_back({-b, till});
}
}
vector<RMQ> lifts(LOG + 1), nrlifts(LOG + 1);
vector<RMQ_MIN> rlifts(LOG + 1);
{
multiset<pair<int, int>> mt;
for (int j = 1; j <= n; ++j) {
for (auto& u : events[j]) {
if (u[0] < 0) {
mt.erase(mt.find({-u[0], u[1]}));
} else {
mt.insert({u[0], u[1]});
}
}
if (mt.size() > 0) {
auto it = prev(mt.end());
lift[j][0] = it->first;
}
}
for (int i = 0; i <= LOG; ++i) {
lifts[i].init(n, -1);
for (int j = 1; j <= n; ++j) {
lifts[i].update_max(j, lift[j][i]);
}
for (int j = 1; j <= n; ++j) {
lift[j][i + 1] = lifts[i].query_max(j, lift[j][i]);
}
}
}
{
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= LOG; ++j) {
lift[i][j] = -1;
}
}
multiset<pair<int, int>> mt;
for (int j = 1; j <= n; ++j) {
for (auto& u : revents[j]) {
if (u[0] < 0) {
mt.erase(mt.find({-u[0], u[1]}));
} else {
mt.insert({u[0], u[1]});
}
}
if (mt.size() > 0) {
auto it = prev(mt.end());
lift[j][0] = it->first;
}
}
for (int i = 0; i <= LOG; ++i) {
nrlifts[i].init(n, -1);
for (int j = 1; j <= n; ++j) {
nrlifts[i].update_max(j, lift[j][i]);
}
for (int j = 1; j <= n; ++j) {
lift[j][i + 1] = nrlifts[i].query_max(j, lift[j][i]);
}
}
for (int j = 0; j <= LOG; ++j) {
rlifts[j].init(n, n);
vector<int> vals;
for (int i = 1; i <= n; ++i) {
int val = nrlifts[j].query_max(i, i);
vals.push_back(val);
}
reverse(begin(vals), end(vals));
for (int i = 1; i <= n; ++i) {
if (vals[i - 1] != -1) {
vals[i - 1] = n - vals[i - 1] + 1;
} else {
vals[i - 1] = n + 1;
}
rlifts[j].update_min(i, vals[i - 1]);
}
}
}
int q;
cin >> q;
while (q--) {
int a, b;
cin >> a >> b;
//~ assert(a < b);
int res = -1;
if (a < b) {
int nxt = a;
int now = 0;
for (int i = LOG; i >= 0; --i) {
int NEXT = lifts[i].query_max(a, nxt);
//~ cerr << a << " -> " << nxt << "\n";
if (NEXT > nxt && NEXT < b) {
nxt = NEXT;
now += (1 << i);
}
}
now += 1;
a = lifts[0].query_max(a, nxt);
//~ cerr << a << " " << b << " = ";
if (a >= b) {
res = now;
}
} else {
int nxt = a;
int now = 0;
//~ cerr << "Query start = " << nxt << " " << a << " to " << b << "\n";
for (int i = LOG; i >= 0; --i) {
int NEXT = rlifts[i].query_min(nxt, a);
//~ cerr << nxt << " -> " << a << "\n";
if (NEXT < nxt && NEXT > b) {
nxt = NEXT;
now += (1 << i);
}
}
now += 1;
a = rlifts[0].query_min(nxt, a);
//~ cerr << a << " " << b << " = ";
if (a <= b) {
res = now;
}
}
cout << res << "\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... |