#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll; typedef pair<int, int> pii;
#define pb emplace_back
#define AI(x) begin(x),end(x)
#define ff first
#define ss second
#ifdef OWO
#define debug(args...) LKJ("\033[0;32m[ " + string(#args) + " ]\033[0m", args)
template<class I> void LKJ(I&&x) { cerr << x << endl; }
template<class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); }
template<class I> void OI(I a, I b) { while (a != b) cerr << *a << ' ', ++a; cerr << endl; }
#else
#define debug(...) 0
#define OI(...) 0
#endif
struct RMQ {
int n; vector<int> val;
RMQ() = default;
void build(const vector<int>& v) {
n = v.size();
val.resize(n * 2);
for (int i = 0; i < n; ++i)
val[i + n] = v[i];
for (int i = n - 1; i > 0; --i)
val[i] = max(val[i << 1], val[i << 1 | 1]);
}
int query(int l, int r) {
++r;
int res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, val[l++]);
if (r & 1) res = max(res, val[--r]);
}
return res;
}
};
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N, K; cin >> N >> K;
int M; cin >> M;
vector<int> A(M + 1), B(M + 1);
for (int i = 1; i <= M; ++i)
cin >> A[i] >> B[i];
int Q; cin >> Q;
vector<int> S(Q + 1), T(Q + 1);
for (int i = 1; i <= Q; ++i)
cin >> S[i] >> T[i];
vector<vector<int>> ono(N + 1);
for (int i = 1; i <= M; ++i) {
assert(A[i] < B[i]);
ono[A[i]].pb(B[i]);
if (A[i] + K <= N)
ono[A[i] + K].pb(-B[i]);
}
multiset<int> st;
vector<int> rightmost(N + 1, 0);
for (int i = 1; i <= N; ++i) {
for (const int& v: ono[i]) {
if (v > 0) st.insert(v);
else {
auto it = st.find(-v);
st.erase(it);
}
}
if (!st.empty())
rightmost[i] = max(i, *rbegin(st));
else
rightmost[i] = i;
}
int lg = __lg(N) + 1;
RMQ rmq;
vector<vector<int>> jmp(lg + 1, vector<int>(N + 1, 0));
jmp[0] = rightmost;
for (int l = 1; l <= lg; ++l) {
rmq.build(jmp[l - 1]);
for (int i = 1; i <= N; ++i) {
int rb = jmp[l - 1][i];
jmp[l][i] = rmq.query(i, rb);
}
debug(l);
OI(AI(jmp[l]));
}
for (int i = 1; i <= Q; ++i) {
int s = S[i], t = T[i];
if (jmp[lg][s] < t) {
cout << -1 << '\n';
continue;
}
int ans = 0;
for (int l = lg; l >= 0; --l)
if (jmp[l][s] < t) {
ans += (1 << l);
s = jmp[l][s];
}
cout << ans + 1 << '\n';
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:14:20: warning: statement has no effect [-Wunused-value]
14 | #define debug(...) 0
| ^
Main.cpp:87:3: note: in expansion of macro 'debug'
87 | debug(l);
| ^~~~~
Main.cpp:15:17: warning: statement has no effect [-Wunused-value]
15 | #define OI(...) 0
| ^
Main.cpp:88:3: note: in expansion of macro 'OI'
88 | OI(AI(jmp[l]));
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
14 ms |
6464 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
21 ms |
7228 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
266 ms |
20232 KB |
Output is correct |
2 |
Correct |
127 ms |
15472 KB |
Output is correct |
3 |
Correct |
102 ms |
13424 KB |
Output is correct |
4 |
Correct |
111 ms |
12328 KB |
Output is correct |
5 |
Correct |
78 ms |
11792 KB |
Output is correct |
6 |
Correct |
108 ms |
11492 KB |
Output is correct |
7 |
Correct |
154 ms |
19988 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
2 ms |
588 KB |
Output is correct |
10 |
Correct |
244 ms |
20180 KB |
Output is correct |
11 |
Correct |
215 ms |
24816 KB |
Output is correct |
12 |
Correct |
258 ms |
20060 KB |
Output is correct |
13 |
Correct |
280 ms |
24512 KB |
Output is correct |
14 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |