#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())
const int INF = 1e9+5;
const int K = 500;
const int MAX = 2e5+1;
int n, L;
int h[MAX], a[MAX], b[MAX], ans[MAX], maxH[MAX], byH[MAX], v[MAX], p[MAX], memo[MAX], lastAdd[MAX];
vector<int> d[MAX];
vector<pair<int, int>> queries[MAX], todo[MAX];
void updV(int i, int val){
v[i] = max(v[i], val);
ans[i/K] = max(ans[i/K], v[i]);
}
void addH(int i){
byH[i] = h[i];
maxH[i/K] = max(maxH[i/K], h[i]);
lastAdd[i/K] = L;
}
void remH(int i){
byH[i] = -INF;
maxH[i/K] = -INF;
for(int j = i-(i%K); j < min(n, i-(i%K)+K); j++){
maxH[i/K] = max(maxH[i/K], byH[j]);
}
for(int j = 0; j < sz(d[i/K]); j++){
if(i-a[i] >= d[i/K][j]){
updV(i, h[i]-h[d[i/K][j]]);
break;
}
}
}
void add_single(int i){
updV(i, byH[i]-h[L]);
}
void add_to_block(int block){
ans[block] = max(ans[block], maxH[block]-h[L]);
if(!d[block].empty()){
if(lastAdd[block] != L && h[d[block].back()] <= h[L]) return;
}
while(!d[block].empty() && h[d[block].back()] > h[L]) d[block].pop_back();
d[block].push_back(L);
}
int qry(int R){
int res = -INF;
int i = L-(L%K);
while(i+K-1 <= R){
res = max(res, ans[i/K]);
i += K;
}
if(i <= R){
int j = 0;
for(; i < min(i+K, n); i++){
int x = p[i];
if(x > R) continue;
res = max(res, v[x]);
if(byH[x] == -INF) continue;
while(j < sz(d[i/K]) && x-a[x] < d[i/K][j]) j++;
if(j < sz(d[i/K])) res = max(res, h[x]-h[d[i/K][j]]);
}
}
return res;
}
void solve(){
for(L = n-1; L >= 0; L--){
for(auto [i, op] : todo[L]){
if(op == 1) addH(i);
else remH(i);
}
int i = L+a[L];
for(; i <= min(L+b[L], n-1) && i % K != 0; i++){
add_single(i);
}
while(i+K-1 <= min(L+b[L], n-1)){
add_to_block(i/K);
i += K;
}
for(; i <= min(L+b[L], n-1); i++){
add_single(i);
}
for(auto [R, ind] : queries[L]){
memo[ind] = max(memo[ind], qry(R));
}
}
}
void init(){
fill_n(ans, n, -INF);
fill_n(maxH, n, -INF);
fill_n(byH, n, -INF);
fill_n(v, n, -INF);
fill_n(lastAdd, n, n);
for(int i = 0; i < MAX; i++) d[i].clear();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
init();
for(int i = 0; i < n; i++){
cin >> h[i] >> a[i] >> b[i];
p[i] = i;
if(i-a[i] >= 0) todo[i-a[i]].emplace_back(i, 1);
if(i-b[i]-1 >= 0) todo[i-b[i]-1].emplace_back(i, -1);
}
for(int i = 0; i < n; i += K){
int j = min(i+K, n);
sort(p+i, p+j, [&](int x, int y){return x-a[x] > y-a[y];});
}
int q;
cin >> q;
fill_n(memo, q, -1);
for(int i = 0; i < q; ++i){
int l, r;
cin >> l >> r;
l--, r--;
queries[l].emplace_back(r, i);
}
solve();
for(int i = 0; i < n; i++) h[i] = -h[i];
init();
solve();
for(int i = 0; i < q; i++) cout << memo[i] << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14420 KB |
Output is correct |
2 |
Correct |
8 ms |
14456 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
9 ms |
14420 KB |
Output is correct |
5 |
Correct |
9 ms |
14420 KB |
Output is correct |
6 |
Correct |
9 ms |
14420 KB |
Output is correct |
7 |
Correct |
9 ms |
14420 KB |
Output is correct |
8 |
Correct |
10 ms |
14492 KB |
Output is correct |
9 |
Correct |
9 ms |
14420 KB |
Output is correct |
10 |
Correct |
10 ms |
14420 KB |
Output is correct |
11 |
Correct |
10 ms |
14420 KB |
Output is correct |
12 |
Correct |
9 ms |
14484 KB |
Output is correct |
13 |
Correct |
9 ms |
14420 KB |
Output is correct |
14 |
Correct |
10 ms |
14488 KB |
Output is correct |
15 |
Correct |
9 ms |
14420 KB |
Output is correct |
16 |
Correct |
9 ms |
14420 KB |
Output is correct |
17 |
Correct |
9 ms |
14464 KB |
Output is correct |
18 |
Correct |
9 ms |
14420 KB |
Output is correct |
19 |
Correct |
9 ms |
14420 KB |
Output is correct |
20 |
Correct |
9 ms |
14492 KB |
Output is correct |
21 |
Correct |
9 ms |
14444 KB |
Output is correct |
22 |
Correct |
11 ms |
14420 KB |
Output is correct |
23 |
Correct |
11 ms |
14392 KB |
Output is correct |
24 |
Correct |
9 ms |
14420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14420 KB |
Output is correct |
2 |
Correct |
8 ms |
14456 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
9 ms |
14420 KB |
Output is correct |
5 |
Correct |
9 ms |
14420 KB |
Output is correct |
6 |
Correct |
9 ms |
14420 KB |
Output is correct |
7 |
Correct |
9 ms |
14420 KB |
Output is correct |
8 |
Correct |
10 ms |
14492 KB |
Output is correct |
9 |
Correct |
9 ms |
14420 KB |
Output is correct |
10 |
Correct |
10 ms |
14420 KB |
Output is correct |
11 |
Correct |
10 ms |
14420 KB |
Output is correct |
12 |
Correct |
9 ms |
14484 KB |
Output is correct |
13 |
Correct |
9 ms |
14420 KB |
Output is correct |
14 |
Correct |
10 ms |
14488 KB |
Output is correct |
15 |
Correct |
9 ms |
14420 KB |
Output is correct |
16 |
Correct |
9 ms |
14420 KB |
Output is correct |
17 |
Correct |
9 ms |
14464 KB |
Output is correct |
18 |
Correct |
9 ms |
14420 KB |
Output is correct |
19 |
Correct |
9 ms |
14420 KB |
Output is correct |
20 |
Correct |
9 ms |
14492 KB |
Output is correct |
21 |
Correct |
9 ms |
14444 KB |
Output is correct |
22 |
Correct |
11 ms |
14420 KB |
Output is correct |
23 |
Correct |
11 ms |
14392 KB |
Output is correct |
24 |
Correct |
9 ms |
14420 KB |
Output is correct |
25 |
Correct |
377 ms |
18200 KB |
Output is correct |
26 |
Correct |
91 ms |
14832 KB |
Output is correct |
27 |
Incorrect |
639 ms |
19464 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
615 ms |
23764 KB |
Output is correct |
2 |
Correct |
579 ms |
29144 KB |
Output is correct |
3 |
Correct |
364 ms |
24944 KB |
Output is correct |
4 |
Correct |
586 ms |
29140 KB |
Output is correct |
5 |
Correct |
282 ms |
21132 KB |
Output is correct |
6 |
Correct |
607 ms |
29252 KB |
Output is correct |
7 |
Correct |
578 ms |
27216 KB |
Output is correct |
8 |
Correct |
582 ms |
29260 KB |
Output is correct |
9 |
Correct |
95 ms |
16724 KB |
Output is correct |
10 |
Correct |
563 ms |
29156 KB |
Output is correct |
11 |
Correct |
416 ms |
23728 KB |
Output is correct |
12 |
Correct |
541 ms |
29328 KB |
Output is correct |
13 |
Correct |
627 ms |
29204 KB |
Output is correct |
14 |
Correct |
533 ms |
28868 KB |
Output is correct |
15 |
Correct |
439 ms |
27876 KB |
Output is correct |
16 |
Correct |
409 ms |
27340 KB |
Output is correct |
17 |
Correct |
614 ms |
29356 KB |
Output is correct |
18 |
Correct |
490 ms |
28068 KB |
Output is correct |
19 |
Correct |
608 ms |
28728 KB |
Output is correct |
20 |
Correct |
571 ms |
28696 KB |
Output is correct |
21 |
Correct |
637 ms |
29168 KB |
Output is correct |
22 |
Correct |
562 ms |
28688 KB |
Output is correct |
23 |
Correct |
470 ms |
28772 KB |
Output is correct |
24 |
Correct |
396 ms |
27336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14420 KB |
Output is correct |
2 |
Correct |
8 ms |
14456 KB |
Output is correct |
3 |
Correct |
8 ms |
14420 KB |
Output is correct |
4 |
Correct |
9 ms |
14420 KB |
Output is correct |
5 |
Correct |
9 ms |
14420 KB |
Output is correct |
6 |
Correct |
9 ms |
14420 KB |
Output is correct |
7 |
Correct |
9 ms |
14420 KB |
Output is correct |
8 |
Correct |
10 ms |
14492 KB |
Output is correct |
9 |
Correct |
9 ms |
14420 KB |
Output is correct |
10 |
Correct |
10 ms |
14420 KB |
Output is correct |
11 |
Correct |
10 ms |
14420 KB |
Output is correct |
12 |
Correct |
9 ms |
14484 KB |
Output is correct |
13 |
Correct |
9 ms |
14420 KB |
Output is correct |
14 |
Correct |
10 ms |
14488 KB |
Output is correct |
15 |
Correct |
9 ms |
14420 KB |
Output is correct |
16 |
Correct |
9 ms |
14420 KB |
Output is correct |
17 |
Correct |
9 ms |
14464 KB |
Output is correct |
18 |
Correct |
9 ms |
14420 KB |
Output is correct |
19 |
Correct |
9 ms |
14420 KB |
Output is correct |
20 |
Correct |
9 ms |
14492 KB |
Output is correct |
21 |
Correct |
9 ms |
14444 KB |
Output is correct |
22 |
Correct |
11 ms |
14420 KB |
Output is correct |
23 |
Correct |
11 ms |
14392 KB |
Output is correct |
24 |
Correct |
9 ms |
14420 KB |
Output is correct |
25 |
Correct |
377 ms |
18200 KB |
Output is correct |
26 |
Correct |
91 ms |
14832 KB |
Output is correct |
27 |
Incorrect |
639 ms |
19464 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |