#include <bits/stdc++.h>
using namespace std;
#pragma region debug
#if defined(LOCAL) && !defined(ONLINE_JUDGE)
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
return os << '(' << p.first << ", " << p.second << ')';
}
template<typename T1, typename T2, typename T3>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3> &p) {
return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ')';
}
template<typename T1, typename T2, typename T3, typename T4>
ostream &operator<<(ostream &os, const tuple<T1, T2, T3, T4> &p) {
return os << '(' << get<0>(p) << ", " << get<1>(p) << ", " << get<2>(p) << ", " << get<3>(p) << ')';
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
os << '[';
if (v.size()) {
os << *v.begin();
for (auto i = next(v.begin()); i != v.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, const deque<T> &d) {
os << '[';
if (d.size()) {
os << *d.begin();
for (auto i = next(d.begin()); i != d.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, stack<T> s) {
os << '[';
if (s.size()) {
int n = s.size();
vector<T> v(n);
for (int i = 0; i < n; i++) {
v[i] = s.top();
s.pop();
}
os << v[n - 1];
for (int i = n - 2; i >= 0; i--)
os << ", " << v[i];
}
return os << "]>";
}
template<typename T>
ostream &operator<<(ostream &os, queue<T> q) {
os << '[';
if (q.size()) {
int n = q.size();
vector<T> v(n);
for (int i = 0; i < n; i++) {
v[i] = q.front();
q.pop();
}
os << v[n - 1];
for (int i = n - 2; i >= 0; i--)
os << ", " << v[i];
}
return os << "]>";
}
template<typename T, size_t N>
ostream &operator<<(ostream &os, const array<T, N> &a) {
os << '[';
if (N) {
os << *a.begin();
for (auto i = next(a.begin()); i != a.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, const set<T> &s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = next(s.begin()); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, const unordered_set<T> &s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = next(s.begin()); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T>
ostream &operator<<(ostream &os, const multiset<T> &s) {
os << '[';
if (s.size()) {
os << *s.begin();
for (auto i = next(s.begin()); i != s.end(); i++)
os << ", " << (*i);
}
return os << ']';
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &m) {
os << '[';
if (m.size()) {
os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
for (auto i = next(m.begin()); i != m.end(); i++)
os << ", " << '(' << i->first << " : " << i->second << ')';
}
return os << ']';
}
template<typename T1, typename T2>
ostream& operator<<(ostream& os, const unordered_map<T1, T2> &m) {
os << '[';
if (m.size()) {
os << '(' << m.begin()->first << " : " << m.begin()->second << ')';
for (auto i = next(m.begin()); i != m.end(); i++)
os << ", " << '(' << i->first << " : " << i->second << ')';
}
return os << ']';
}
map<char, string> _dbg_dict {
{'1', "--------------------------------"},
{'2', "================================"},
{'3', "≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡"},
{'4', "################################"},
{'*', "********************************"},
{'_', "_"},
{'<', "<!---- "},
{'>', " ----!>"},
{'(', "(!==== "},
{')', "==== !)"},
{'[', "[!≡≡≡≡ "},
{']', " ≡≡≡≡!]"},
{'{', "{!#### "},
{'}', " ####!}"},
{'c', "checkpoint "},
{'l', "line "},
{'n', "\n"},
{'t', "\t"}
};
template<typename T>
void _dbg_print(string var, const T &a) { cerr << var << " = " << a << '\n'; }
void _dbg_print(string var, const char *a) {
int n = strlen(a);
for (int i = 0; i < n; i++)
cerr << (i < n - 1 && a[i] == '_' && _dbg_dict.find(a[i + 1]) != _dbg_dict.end() ? _dbg_dict[a[++i]] : string(1, a[i]));
}
#define dbg1(a) _dbg_print(#a, a);
#define dbg2(a, b) dbg1(a) dbg1(b)
#define dbg3(a, b, c) dbg1(a) dbg2(b, c)
#define dbg4(a, b, c, d) dbg1(a) dbg3(b, c, d)
#define dbg5(a, b, c, d, e) dbg1(a) dbg4(b, c, d, e)
#define dbg6(a, b, c, d, e, f) dbg1(a) dbg5(b, c, d, e, f)
#define dbg7(a, b, c, d, e, f, g) dbg1(a) dbg6(b, c, d, e, f, g)
#define dbg8(a, b, c, d, e, f, g, h) dbg1(a) dbg7(b, c, d, e, f, g, h)
#define dbg9(a, b, c, d, e, f, g, h, i) dbg1(a) dbg8(b, c, d, e, f, g, h, i)
#define dbg10(a, b, c, d, e, f, g, h, i, j) dbg1(a) dbg9(b, c, d, e, f, g, h, i, j)
#define dbg11(a, b, c, d, e, f, g, h, i, j, k) dbg1(a) dbg10(b, c, d, e, f, g, h, i, j, k)
#define dbg12(a, b, c, d, e, f, g, h, i, j, k, l) dbg1(a) dbg11(b, c, d, e, f, g, h, i, j, k, l)
#define dbg13(a, b, c, d, e, f, g, h, i, j, k, l, m) dbg1(a) dbg12(b, c, d, e, f, g, h, i, j, k, l, m)
#define dbg14(a, b, c, d, e, f, g, h, i, j, k, l, m, n) dbg1(a) dbg13(b, c, d, e, f, g, h, i, j, k, l, m, n)
#define dbg15(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o) dbg1(a) dbg14(b, c, d, e, f, g, h, i, j, k, l, m, n, o)
#define dbg16(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p) dbg1(a) dbg15(b, c, d, e, f, g, h, i, j, k, l, m, n, o, p)
#define get_dbg(_1, _2, _3, _4, _5, _6, _7, _8, _9, _10, _11, _12, _13, _14, _15, _16, NAME, ...) NAME
#define dbg(...) get_dbg(__VA_ARGS__, dbg16, dbg15, dbg14, dbg13, dbg12, dbg11, dbg10, dbg9, dbg8, \
dbg7, dbg6, dbg5, dbg4, dbg3, dbg2, dbg1)(__VA_ARGS__)
#else
#define cerr if (false) cerr
#define dbg(...)
#endif
#pragma endregion debug
const int $L = 7;
int main() {
int N, K, M;
cin >> N >> K >> M;
array<vector<int>, $L> lb, rb;
lb.fill(vector<int>(2 * N, -1));
rb.fill(vector<int>(2 * N, -1));
vector<int> A(M), B(M);
for (int i = 0; i < M; i++) {
cin >> A[i] >> B[i];
A[i]--, B[i]--;
}
multiset<int> mse;
vector<vector<int>> ins(N), era(N);
for (int i = 0; i < M; i++) {
if (A[i] > B[i]) {
ins[A[i]].push_back(B[i]);
era[max(A[i] - K + 1, B[i] + 1)].push_back(B[i]);
}
// if (A[i] < B[i]) {
// ins[min(A[i] + K - 1, B[i] - 1)].push_back(A[i]);
// era[A[i]].push_back(A[i]);
// }
}
for (int i = N - 1; i >= 0; i--) {
for (int k : ins[i])
mse.insert(k);
ins[i].clear();
lb[0][i + N] = min(i, mse.empty() ? N : *mse.begin());
for (int k : era[i])
mse.erase(mse.find(k));
era[i].clear();
}
assert(mse.empty());
for (int i = 0; i < M; i++) {
if (A[i] < B[i]) {
ins[A[i]].push_back(B[i]);
era[min(A[i] + K - 1, B[i] - 1)].push_back(B[i]);
}
// if (A[i] > B[i]) {
// ins[max(A[i] - K + 1, B[i] + 1)].push_back(A[i]);
// era[A[i]].push_back(A[i]);
// }
}
for (int i = 0; i < N; i++) {
for (int k : ins[i])
mse.insert(k);
ins[i].clear();
rb[0][i + N] = max(i, mse.empty() ? 0 : *mse.rbegin());
for (int k : era[i])
mse.erase(mse.find(k));
era[i].clear();
}
assert(mse.empty());
for (int b = 1; b < $L; b++) {
for (int i = N - 1; i >= 1; i--) {
lb[b - 1][i] = min(lb[b - 1][i * 2], lb[b - 1][i * 2 + 1]);
rb[b - 1][i] = max(rb[b - 1][i * 2], rb[b - 1][i * 2 + 1]);
}
for (int i = 0; i < N; i++) {
int l = lb[b - 1][i + N], r = rb[b - 1][i + N];
int retl = N, retr = 0;
for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
retl = min(retl, lb[b - 1][l]);
retr = max(retr, rb[b - 1][l]);
l++;
}
if (r & 1) {
r--;
retl = min(retl, lb[b - 1][r]);
retr = max(retr, rb[b - 1][r]);
}
}
lb[b][i + N] = retl, rb[b][i + N] = retr;
}
}
// for (int i = 0; i < $L; i++) {
// vector<int> l(lb[i].begin() + N, lb[i].end());
// vector<int> r(rb[i].begin() + N, rb[i].end());
// dbg("_1\n", i, l, r);
// }
int Q;
cin >> Q;
while (Q--) {
int u, v;
cin >> u >> v;
u--, v--;
if (v < lb[$L - 1][u + N] || rb[$L - 1][u + N] < v) {
cout << -1 << '\n';
} else {
if (u == v) {
cout << 0 << '\n';
} else if (u < v) {
int ans = 0;
for (int b = $L - 1; b >= 0; b--) {
if (rb[b][u + N] < v) {
u = rb[b][u + N];
ans |= (1 << b);
}
}
cout << ans + 1 << '\n';
} else if (u > v) {
int ans = 0;
for (int b = $L - 1; b >= 0; b--) {
if (v < lb[b][u + N]) {
u = lb[b][u + N];
ans |= (1 << b);
}
}
cout << ans + 1 << '\n';
}
}
}
}
Compilation message
Main.cpp:4: warning: ignoring '#pragma region debug' [-Wunknown-pragmas]
4 | #pragma region debug
|
Main.cpp:198: warning: ignoring '#pragma endregion debug' [-Wunknown-pragmas]
198 | #pragma endregion debug
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
103 ms |
22636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
187 ms |
24472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
347 ms |
27924 KB |
Output is correct |
| 2 |
Incorrect |
189 ms |
24840 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
