#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int inf = 1e9 + 100;
int n, Q;
///SEGMENT TREE BEGIN
struct node{
int s, e, m, C, lazy, D;
node *l, *r;
node(int _s, int _e){
s = _s; e = _e;
m = (s+e)/2;
C = -inf, lazy = inf, D = -inf;
if(s != e){
l = new node(s, m);
r = new node(m+1, e);
}
}
void push(){
if(lazy != inf){
l->lazy = min(l->lazy, lazy);
r->lazy = min(r->lazy, lazy);
l->D = max(l->D, l->C - lazy);
r->D = max(r->D, r->C - lazy);
lazy = inf;
}
}
void pull(){
C = max(l->C, r->C);
D = max(l->D, r->D);
}
void updateC(int i, int H){
if(s == e){
C = H;
return;
}
push();
if(i <= m) l->updateC(i, H);
else r->updateC(i, H);
pull();
}
void updateLazy(int L, int R, int H){
if(s == L && e == R){
D = max(D, C - H);
lazy = min(lazy, H);
return;
}
push();
if(R <= m) l->updateLazy(L, R, H);
else if(L >= m+1) r->updateLazy(L, R, H);
else{
l->updateLazy(L, m, H);
r->updateLazy(m+1, R, H);
}
pull();
}
int query(int L, int R){
//if(s == 0 && e == n-1) cout << "Q: " << L << " " << R <<"\n";
if(s == L && e == R) return D;
push();
if(R <= m) return l->query(L, R);
else if(L >= m+1) return r->query(L, R);
else{
return max(l->query(L, m), r->query(m+1, R));
}
}
} *root;
///SEGMENT TREE END
int H[200005];
int A[200005];
int B[200005];
int ans[200005];
ii QQ[200005];
vector<ii> queries[200005];
vector<ii> events[200005];
void solve(){
for(int i = 0;i < n;i++) events[i].clear();
for(int i = 0;i < n;i++) queries[i].clear();
root = new node(0, n-1);
for(int i = 0;i < n;i++){
int start = i + A[i], end = i + B[i] + 1;
if(start < n) events[start].push_back(ii(i, 1)); ///1 is start
if(end < n) events[end].push_back(ii(i, -1)); ///-1 is end
}
for(int i = 0;i < Q;i++){
queries[QQ[i].second].push_back(ii(QQ[i].first, i));
}
for(int r = 0;r < n;r++){
//cout << r << ":\n";
sort(events[r].begin(),events[r].end());
for(ii e : events[r]){
if(e.second == 1) root->updateC(e.first, H[e.first]);
else root->updateC(e.first, -inf);
}
if(r - A[r] >= 0){
int R = r - A[r];
int L = max(0, r - B[r]);
root->updateLazy(L, R, H[r]);
}
for(ii q : queries[r]){
int res = root->query(q.first, r);
//cout << q.second << " " << q.first << " " << r << " " << res << "\n";
ans[q.second] = max(ans[q.second],res);
}
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 0;i < n;i++) cin >> H[i] >> A[i] >> B[i];
cin >> Q;
fill(ans,ans+Q, -inf);
for(int i = 0;i < Q;i++){
int l, r; cin >> l >> r; l--; r--;
QQ[i] = ii(l,r);
}
solve();
reverse(H,H+n);
reverse(A,A+n);
reverse(B,B+n);
for(int i = 0;i < Q;i++){
QQ[i].first = n - 1 - QQ[i].first;
QQ[i].second = n - 1 - QQ[i].second;
swap(QQ[i].first,QQ[i].second);
}
solve();
for(int i = 0;i < Q;i++) cout << max(-1,ans[i]) << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9856 KB |
Output is correct |
2 |
Correct |
11 ms |
9856 KB |
Output is correct |
3 |
Correct |
10 ms |
9856 KB |
Output is correct |
4 |
Correct |
10 ms |
9856 KB |
Output is correct |
5 |
Correct |
10 ms |
9856 KB |
Output is correct |
6 |
Correct |
10 ms |
9856 KB |
Output is correct |
7 |
Correct |
12 ms |
9856 KB |
Output is correct |
8 |
Correct |
10 ms |
9856 KB |
Output is correct |
9 |
Correct |
10 ms |
9796 KB |
Output is correct |
10 |
Correct |
11 ms |
9856 KB |
Output is correct |
11 |
Correct |
10 ms |
9728 KB |
Output is correct |
12 |
Correct |
11 ms |
9856 KB |
Output is correct |
13 |
Correct |
11 ms |
9856 KB |
Output is correct |
14 |
Correct |
10 ms |
9856 KB |
Output is correct |
15 |
Correct |
10 ms |
9856 KB |
Output is correct |
16 |
Correct |
10 ms |
9856 KB |
Output is correct |
17 |
Correct |
11 ms |
9856 KB |
Output is correct |
18 |
Correct |
10 ms |
9856 KB |
Output is correct |
19 |
Correct |
10 ms |
9856 KB |
Output is correct |
20 |
Correct |
10 ms |
9856 KB |
Output is correct |
21 |
Correct |
10 ms |
9856 KB |
Output is correct |
22 |
Correct |
10 ms |
9856 KB |
Output is correct |
23 |
Correct |
10 ms |
9856 KB |
Output is correct |
24 |
Correct |
10 ms |
9856 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9856 KB |
Output is correct |
2 |
Correct |
11 ms |
9856 KB |
Output is correct |
3 |
Correct |
10 ms |
9856 KB |
Output is correct |
4 |
Correct |
10 ms |
9856 KB |
Output is correct |
5 |
Correct |
10 ms |
9856 KB |
Output is correct |
6 |
Correct |
10 ms |
9856 KB |
Output is correct |
7 |
Correct |
12 ms |
9856 KB |
Output is correct |
8 |
Correct |
10 ms |
9856 KB |
Output is correct |
9 |
Correct |
10 ms |
9796 KB |
Output is correct |
10 |
Correct |
11 ms |
9856 KB |
Output is correct |
11 |
Correct |
10 ms |
9728 KB |
Output is correct |
12 |
Correct |
11 ms |
9856 KB |
Output is correct |
13 |
Correct |
11 ms |
9856 KB |
Output is correct |
14 |
Correct |
10 ms |
9856 KB |
Output is correct |
15 |
Correct |
10 ms |
9856 KB |
Output is correct |
16 |
Correct |
10 ms |
9856 KB |
Output is correct |
17 |
Correct |
11 ms |
9856 KB |
Output is correct |
18 |
Correct |
10 ms |
9856 KB |
Output is correct |
19 |
Correct |
10 ms |
9856 KB |
Output is correct |
20 |
Correct |
10 ms |
9856 KB |
Output is correct |
21 |
Correct |
10 ms |
9856 KB |
Output is correct |
22 |
Correct |
10 ms |
9856 KB |
Output is correct |
23 |
Correct |
10 ms |
9856 KB |
Output is correct |
24 |
Correct |
10 ms |
9856 KB |
Output is correct |
25 |
Correct |
88 ms |
16508 KB |
Output is correct |
26 |
Correct |
22 ms |
11008 KB |
Output is correct |
27 |
Correct |
124 ms |
19320 KB |
Output is correct |
28 |
Correct |
123 ms |
19324 KB |
Output is correct |
29 |
Correct |
84 ms |
16760 KB |
Output is correct |
30 |
Correct |
94 ms |
16504 KB |
Output is correct |
31 |
Correct |
95 ms |
18168 KB |
Output is correct |
32 |
Correct |
124 ms |
19192 KB |
Output is correct |
33 |
Correct |
114 ms |
18812 KB |
Output is correct |
34 |
Correct |
66 ms |
14584 KB |
Output is correct |
35 |
Correct |
124 ms |
19576 KB |
Output is correct |
36 |
Correct |
123 ms |
19320 KB |
Output is correct |
37 |
Correct |
79 ms |
14968 KB |
Output is correct |
38 |
Correct |
122 ms |
18296 KB |
Output is correct |
39 |
Correct |
28 ms |
11392 KB |
Output is correct |
40 |
Correct |
121 ms |
18296 KB |
Output is correct |
41 |
Correct |
94 ms |
16376 KB |
Output is correct |
42 |
Correct |
123 ms |
18208 KB |
Output is correct |
43 |
Correct |
48 ms |
13048 KB |
Output is correct |
44 |
Correct |
122 ms |
18296 KB |
Output is correct |
45 |
Correct |
32 ms |
11640 KB |
Output is correct |
46 |
Correct |
123 ms |
18272 KB |
Output is correct |
47 |
Correct |
40 ms |
12280 KB |
Output is correct |
48 |
Correct |
123 ms |
18296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
438 ms |
49912 KB |
Output is correct |
2 |
Correct |
470 ms |
54392 KB |
Output is correct |
3 |
Correct |
313 ms |
41080 KB |
Output is correct |
4 |
Correct |
484 ms |
54392 KB |
Output is correct |
5 |
Correct |
190 ms |
30328 KB |
Output is correct |
6 |
Correct |
509 ms |
54264 KB |
Output is correct |
7 |
Correct |
427 ms |
48548 KB |
Output is correct |
8 |
Correct |
497 ms |
54392 KB |
Output is correct |
9 |
Correct |
61 ms |
17528 KB |
Output is correct |
10 |
Correct |
524 ms |
58872 KB |
Output is correct |
11 |
Correct |
275 ms |
40440 KB |
Output is correct |
12 |
Correct |
506 ms |
58744 KB |
Output is correct |
13 |
Correct |
235 ms |
58992 KB |
Output is correct |
14 |
Correct |
228 ms |
58804 KB |
Output is correct |
15 |
Correct |
215 ms |
57752 KB |
Output is correct |
16 |
Correct |
207 ms |
57788 KB |
Output is correct |
17 |
Correct |
233 ms |
59436 KB |
Output is correct |
18 |
Correct |
226 ms |
58308 KB |
Output is correct |
19 |
Correct |
234 ms |
58604 KB |
Output is correct |
20 |
Correct |
232 ms |
58556 KB |
Output is correct |
21 |
Correct |
219 ms |
58728 KB |
Output is correct |
22 |
Correct |
225 ms |
58480 KB |
Output is correct |
23 |
Correct |
223 ms |
58736 KB |
Output is correct |
24 |
Correct |
211 ms |
57200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9856 KB |
Output is correct |
2 |
Correct |
11 ms |
9856 KB |
Output is correct |
3 |
Correct |
10 ms |
9856 KB |
Output is correct |
4 |
Correct |
10 ms |
9856 KB |
Output is correct |
5 |
Correct |
10 ms |
9856 KB |
Output is correct |
6 |
Correct |
10 ms |
9856 KB |
Output is correct |
7 |
Correct |
12 ms |
9856 KB |
Output is correct |
8 |
Correct |
10 ms |
9856 KB |
Output is correct |
9 |
Correct |
10 ms |
9796 KB |
Output is correct |
10 |
Correct |
11 ms |
9856 KB |
Output is correct |
11 |
Correct |
10 ms |
9728 KB |
Output is correct |
12 |
Correct |
11 ms |
9856 KB |
Output is correct |
13 |
Correct |
11 ms |
9856 KB |
Output is correct |
14 |
Correct |
10 ms |
9856 KB |
Output is correct |
15 |
Correct |
10 ms |
9856 KB |
Output is correct |
16 |
Correct |
10 ms |
9856 KB |
Output is correct |
17 |
Correct |
11 ms |
9856 KB |
Output is correct |
18 |
Correct |
10 ms |
9856 KB |
Output is correct |
19 |
Correct |
10 ms |
9856 KB |
Output is correct |
20 |
Correct |
10 ms |
9856 KB |
Output is correct |
21 |
Correct |
10 ms |
9856 KB |
Output is correct |
22 |
Correct |
10 ms |
9856 KB |
Output is correct |
23 |
Correct |
10 ms |
9856 KB |
Output is correct |
24 |
Correct |
10 ms |
9856 KB |
Output is correct |
25 |
Correct |
88 ms |
16508 KB |
Output is correct |
26 |
Correct |
22 ms |
11008 KB |
Output is correct |
27 |
Correct |
124 ms |
19320 KB |
Output is correct |
28 |
Correct |
123 ms |
19324 KB |
Output is correct |
29 |
Correct |
84 ms |
16760 KB |
Output is correct |
30 |
Correct |
94 ms |
16504 KB |
Output is correct |
31 |
Correct |
95 ms |
18168 KB |
Output is correct |
32 |
Correct |
124 ms |
19192 KB |
Output is correct |
33 |
Correct |
114 ms |
18812 KB |
Output is correct |
34 |
Correct |
66 ms |
14584 KB |
Output is correct |
35 |
Correct |
124 ms |
19576 KB |
Output is correct |
36 |
Correct |
123 ms |
19320 KB |
Output is correct |
37 |
Correct |
79 ms |
14968 KB |
Output is correct |
38 |
Correct |
122 ms |
18296 KB |
Output is correct |
39 |
Correct |
28 ms |
11392 KB |
Output is correct |
40 |
Correct |
121 ms |
18296 KB |
Output is correct |
41 |
Correct |
94 ms |
16376 KB |
Output is correct |
42 |
Correct |
123 ms |
18208 KB |
Output is correct |
43 |
Correct |
48 ms |
13048 KB |
Output is correct |
44 |
Correct |
122 ms |
18296 KB |
Output is correct |
45 |
Correct |
32 ms |
11640 KB |
Output is correct |
46 |
Correct |
123 ms |
18272 KB |
Output is correct |
47 |
Correct |
40 ms |
12280 KB |
Output is correct |
48 |
Correct |
123 ms |
18296 KB |
Output is correct |
49 |
Correct |
438 ms |
49912 KB |
Output is correct |
50 |
Correct |
470 ms |
54392 KB |
Output is correct |
51 |
Correct |
313 ms |
41080 KB |
Output is correct |
52 |
Correct |
484 ms |
54392 KB |
Output is correct |
53 |
Correct |
190 ms |
30328 KB |
Output is correct |
54 |
Correct |
509 ms |
54264 KB |
Output is correct |
55 |
Correct |
427 ms |
48548 KB |
Output is correct |
56 |
Correct |
497 ms |
54392 KB |
Output is correct |
57 |
Correct |
61 ms |
17528 KB |
Output is correct |
58 |
Correct |
524 ms |
58872 KB |
Output is correct |
59 |
Correct |
275 ms |
40440 KB |
Output is correct |
60 |
Correct |
506 ms |
58744 KB |
Output is correct |
61 |
Correct |
235 ms |
58992 KB |
Output is correct |
62 |
Correct |
228 ms |
58804 KB |
Output is correct |
63 |
Correct |
215 ms |
57752 KB |
Output is correct |
64 |
Correct |
207 ms |
57788 KB |
Output is correct |
65 |
Correct |
233 ms |
59436 KB |
Output is correct |
66 |
Correct |
226 ms |
58308 KB |
Output is correct |
67 |
Correct |
234 ms |
58604 KB |
Output is correct |
68 |
Correct |
232 ms |
58556 KB |
Output is correct |
69 |
Correct |
219 ms |
58728 KB |
Output is correct |
70 |
Correct |
225 ms |
58480 KB |
Output is correct |
71 |
Correct |
223 ms |
58736 KB |
Output is correct |
72 |
Correct |
211 ms |
57200 KB |
Output is correct |
73 |
Correct |
683 ms |
63792 KB |
Output is correct |
74 |
Correct |
516 ms |
60152 KB |
Output is correct |
75 |
Correct |
623 ms |
56184 KB |
Output is correct |
76 |
Correct |
834 ms |
71708 KB |
Output is correct |
77 |
Correct |
405 ms |
40952 KB |
Output is correct |
78 |
Correct |
776 ms |
68088 KB |
Output is correct |
79 |
Correct |
742 ms |
64888 KB |
Output is correct |
80 |
Correct |
837 ms |
71544 KB |
Output is correct |
81 |
Correct |
256 ms |
27620 KB |
Output is correct |
82 |
Correct |
662 ms |
65912 KB |
Output is correct |
83 |
Correct |
571 ms |
52256 KB |
Output is correct |
84 |
Correct |
850 ms |
71688 KB |
Output is correct |
85 |
Correct |
438 ms |
66660 KB |
Output is correct |
86 |
Correct |
551 ms |
70324 KB |
Output is correct |
87 |
Correct |
276 ms |
60128 KB |
Output is correct |
88 |
Correct |
551 ms |
69472 KB |
Output is correct |
89 |
Correct |
477 ms |
68552 KB |
Output is correct |
90 |
Correct |
577 ms |
69960 KB |
Output is correct |
91 |
Correct |
346 ms |
63372 KB |
Output is correct |
92 |
Correct |
568 ms |
70376 KB |
Output is correct |
93 |
Correct |
289 ms |
61380 KB |
Output is correct |
94 |
Correct |
555 ms |
70256 KB |
Output is correct |
95 |
Correct |
337 ms |
62576 KB |
Output is correct |
96 |
Correct |
577 ms |
68976 KB |
Output is correct |