#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;
}
/*struct Node {
int value, index;
bool active = false;
};
Node operator+(Node lhs, Node rhs) {
if (!lhs.active) return rhs;
if (!rhs.active) return lhs;
if (lhs.value < rhs.value) return lhs;
return rhs;
}
Node st[2 * SZ];
int lazy[2 * SZ];
void pass(int u) {
if (lazy[u] == INF) return;
if (u < SZ) {
lazy[2 * u] = min(lazy[2 * u], lazy[u]);
lazy[2 * u + 1] = min(lazy[2 * u + 1], lazy[u]);
}
st[u].value = min(st[u].value, lazy[u]);
lazy[u] = INF;
}
void updateRange(int s, int e, int v, int l = 0, int r = SZ, int u = 1) {
pass(u);
if (e <= l || r <= s) {
return;
}
if (s <= l && r <= e) {
lazy[u] = v;
return pass(u);
}
int m = (l + r) / 2;
updateRange(s, e, v, l, m, 2 * u);
updateRange(s, e, v, m, r, 2 * u + 1);
st[u] = st[2 * u] + st[2 * u + 1];
}
void deactivate(int p, int l = 0, int r = SZ, int u = 1) {
pass(u);
if (u >= SZ) {
st[u].active = false;
return;
}
int m = (l + r) / 2;
if (p < m) deactivate(p, l, m, 2 * u);
else deactivate(p, m, r, 2 * u + 1);
pass(2 * u), pass(2 * u + 1);
st[u] = st[2 * u] + st[2 * u + 1];
}*/
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;
}
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]);
}
//forn(i, n) cerr << left[i] << ' ' << right[i] << '\n';
int q;
cin >> q;
forn(_, q) {
int s, t;
cin >> s >> t;
--s, --t;
int dist = 1;
int l = left[s], r = right[s];
bool flag = true;
while (l > t || r < t) {
//cerr << l << ' ' << r << '\n';
int newL = askMin(l, r + 1);
int newR = askMax(l, r + 1);
if (l == newL && r == newR) {
flag = false;
break;
}
dist++, l = newL, r = newR;
}
if (flag) 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... |