#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
template<typename T>
struct SparseTable {
vector<vector<T>> st;
T (*F) (T, T);
int len;
void init(vector<T> &a, T(*f)(T, T)) {
len = (int)a.size();
int mxpow = 32 - __builtin_clz(len);
F = f;
st.resize(mxpow);
st[0] = a;
for(int k = 1; k < mxpow; k++) {
st[k].resize(len - (1 << k) + 1);
for(int i = 0; i < (int)st[k].size(); i++)
st[k][i] = F(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
}
}
T get(int l, int r) {
if(l > r || l < 0 || r >= len) {
cerr << "Wrong range in Sparse Table\n";
exit(0);
}
int k = 31 - __builtin_clz(r - l + 1);
return F(st[k][l], st[k][r - (1 << k) + 1]);
}
};
int n, k, m;
int A[N], B[N];
int rb[N];
SparseTable<pair<int, int>> st;
void calculate() {
static vector<int> op[N], cl[N];
for(int i = 0; i < m; i++) {
op[A[i]].push_back(B[i]);
cl[min(B[i] + 1, A[i] + k)].push_back(B[i]);
}
multiset<int> ms;
for(int i = 1; i <= n; i++) {
for(int x : cl[i])
ms.erase(ms.find(x));
for(int x : op[i])
ms.insert(x);
rb[i] = (ms.empty() ? i : *(--ms.end()));
}
vector<pair<int, int>> t(n + 1);
for(int i = 1; i <= n; i++) {
t[i] = {rb[i], i};
}
st.init(t, [](pair<int, int> x, pair<int, int> y) {return (x > y ? x : y);});
}
int f[N][20];
void build() {
for(int i = n; i >= 1; i--) {
f[i][0] = i;
for(int k = 1; k < 20; k++) {
int p = st.get(f[i][k - 1], rb[f[i][k - 1]]).second;
f[i][k] = f[p][k - 1];
}
// cout << i << ": ";
// for(int k = 0; k < 4; k++)
// cout << f[i][k] << ' ';
// cout << '\n';
// cout << '\n';
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> k >> m;
bool flag = 0;
for(int i = 0; i < m; i++) {
cin >> A[i] >> B[i];
flag |= (A[i] > B[i]);
}
if(flag) {
cout << "WA\n";
return 0;
}
calculate();
build();
// for(int i = 1; i <= n; i++)
// cout << rb[i] << ' ';
// cout << '\n';
// return 0;
int q;
cin >> q;
while(q--) {
int s, t, ans = 0;
cin >> s >> t;
for(int k = 19; k >= 0; k--) {
if(rb[f[s][k]] < t) s = f[f[s][k]][1], ans += (1 << k);
}
// s = f[s][1], ans++;
// cout << s << ' ' << ans << '\n';
if(rb[s] < t) ans = -1;
else ans += (s < t);
cout << ans << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
9 ms |
980 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
9 ms |
864 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
97 ms |
29944 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |