#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;
const int SZ = 1 << 17;
const int INF = 1e9;
int maxi[2 * SZ], mini[2 * SZ];
template<typename T>
void chmin(T &x, T v) {
if (x > v) x = v;
}
template<typename T>
void chmax(T &x, T v) {
if (x < v) x = v;
}
void update(int l, int r, int v) {
//cerr << l << ' ' << r << ' ' << v << '\n';
for (l += SZ, r += SZ; l < r; l /= 2, r /= 2) {
if (l & 1) {
chmax(maxi[l], v);
chmin(mini[l], v);
l++;
}
if (r & 1) {
--r;
chmax(maxi[r], v);
chmin(mini[r], v);
}
}
}
int queryMax(int i) {
int res = maxi[i += SZ];
while (i /= 2) chmax(res, maxi[i]);
return res;
}
int queryMin(int i) {
int res = mini[i += SZ];
while (i /= 2) chmin(res, mini[i]);
return res;
}
int askMin(int l, int r) {
int res = INF;
for (l += SZ, r += SZ; l < r; l /= 2, r /= 2) {
if (l & 1) chmin(res, mini[l++]);
if (r & 1) chmin(res, mini[--r]);
}
return res;
}
int askMax(int l, int r) {
int res = -INF;
for (l += SZ, r += SZ; l < r; l /= 2, r /= 2) {
if (l & 1) chmax(res, maxi[l++]);
if (r & 1) chmax(res, maxi[--r]);
}
return res;
}
map<pair<ii, int>, ii> memo;
ii up(ii p, int k) {
pair<ii, int> u = {p, k};
if (memo.count(u)) return memo[u];
if (k == 0) {
auto [l, r] = p;
int newL = askMin(l, r + 1);
int newR = askMax(l, r + 1);
ii newP = {newL, newR};
return memo[u] = newP;
}
return memo[u] = up(up(p, k - 1), k - 1);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, k, m;
cin >> n >> k >> m;
forn(i, 2 * SZ) mini[i] = INF, maxi[i] = -INF;
forn(i, n) update(i, i + 1, i);
forn(i, m) {
int a, b;
cin >> a >> b;
--a, --b;
if (a < b) {
update(a, min(a + k, b), b);
} else {
update(max(a - k + 1, b + 1), a + 1, b);
}
}
vi left(n), right(n);
forn(i, n) left[i] = queryMin(i);
forn(i, n) right[i] = queryMax(i);
forn(i, 2 * SZ) mini[i] = INF, maxi[i] = -INF;
forn(i, n) mini[i + SZ] = left[i], maxi[i + SZ] = right[i];
dforsn(i, 1, SZ) {
mini[i] = min(mini[2 * i], mini[2 * i + 1]);
maxi[i] = max(maxi[2 * i], maxi[2 * i + 1]);
}
int q;
cin >> q;
forn(_, q) {
int s, t;
cin >> s >> t;
--s, --t;
int dist = 1;
ii p = {s, s};
dforn(k, 20) {
ii newP = up(p, k);
if (!(newP.fst <= t && t <= newP.snd)) {
p = newP;
dist += 1 << k;
}
}
p = up(p, 0);
if (p.fst <= t && t <= p.snd) cout << dist << '\n';
else cout << "-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... |