#include <bits/stdc++.h>
using namespace std;
const int mxN=2e5, oo=1<<30;
int n, q, h[mxN], a[mxN], b[mxN], ans[mxN], ql[mxN], qr[mxN], lz[1<<19];
vector<int> ta[mxN], tu1[2*mxN], tu2[2*mxN];
array<int, 2> st[1<<19];
void app(int i, int x) {
st[i][1]=max(st[i][0]+x, st[i][1]);
lz[i]=max(x, lz[i]);
}
void psh(int i) {
app(2*i, lz[i]);
app(2*i+1, lz[i]);
lz[i]=-oo;
}
void upd1(int l1, int x, int i=1, int l2=0, int r2=n-1) {
if(l2==r2) {
st[i][0]=x;
return;
}
psh(i);
int m2=(l2+r2)/2;
if(l1<=m2)
upd1(l1, x, 2*i, l2, m2);
else
upd1(l1, x, 2*i+1, m2+1, r2);
st[i][0]=max(st[2*i][0], st[2*i+1][0]);
st[i][1]=max(st[2*i][1], st[2*i+1][1]);
}
void upd2(int l1, int r1, int x, int i=1, int l2=0, int r2=n-1) {
if(l1<=l2&&r2<=r1) {
app(i, x);
return;
}
int m2=(l2+r2)/2;
psh(i);
if(l1<=m2)
upd2(l1, r1, x, 2*i, l2, m2);
if(m2<r1)
upd2(l1, r1, x, 2*i+1, m2+1, r2);
st[i][0]=max(st[2*i][0], st[2*i+1][0]);
st[i][1]=max(st[2*i][1], st[2*i+1][1]);
}
int qry(int l1, int i=1, int l2=0, int r2=n-1) {
if(l1<=l2)
return st[i][1];
int m2=(l2+r2)/2;
psh(i);
return max(l1<=m2?qry(l1, 2*i, l2, m2):-oo, qry(l1, 2*i+1, m2+1, r2));
}
void solve() {
memset(st, 0xc0, sizeof(st));
memset(lz, 0xc0, sizeof(lz));
for(int i=0; i<n; ++i) {
for(int j : tu1[i])
upd1(j, -h[j]);
if(i-a[i]>=0)
upd2(max(i-b[i], 0), i-a[i], h[i]);
for(int j : ta[i])
ans[j]=max(qry(ql[j]), ans[j]);
for(int j : tu2[i])
upd1(j, -oo);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i=0; i<n; ++i) {
cin >> h[i] >> a[i] >> b[i];
tu1[i+a[i]].push_back(i);
tu2[i+b[i]].push_back(i);
}
cin >> q;
memset(ans, -1, 4*q);
for(int i=0; i<q; ++i) {
cin >> ql[i] >> qr[i], --ql[i], --qr[i];
ta[qr[i]].push_back(i);
}
solve();
for(int i=0; i<n; ++i)
h[i]=-h[i];
solve();
for(int i=0; i<q; ++i)
cout << ans[i] << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
29952 KB |
Output is correct |
2 |
Correct |
29 ms |
30072 KB |
Output is correct |
3 |
Correct |
27 ms |
30080 KB |
Output is correct |
4 |
Correct |
28 ms |
30076 KB |
Output is correct |
5 |
Correct |
28 ms |
30072 KB |
Output is correct |
6 |
Correct |
27 ms |
30072 KB |
Output is correct |
7 |
Correct |
28 ms |
30080 KB |
Output is correct |
8 |
Correct |
27 ms |
30072 KB |
Output is correct |
9 |
Correct |
27 ms |
30080 KB |
Output is correct |
10 |
Correct |
29 ms |
30080 KB |
Output is correct |
11 |
Correct |
29 ms |
29952 KB |
Output is correct |
12 |
Correct |
29 ms |
30072 KB |
Output is correct |
13 |
Correct |
27 ms |
30080 KB |
Output is correct |
14 |
Correct |
28 ms |
30080 KB |
Output is correct |
15 |
Correct |
29 ms |
30072 KB |
Output is correct |
16 |
Correct |
28 ms |
30072 KB |
Output is correct |
17 |
Correct |
29 ms |
30080 KB |
Output is correct |
18 |
Correct |
29 ms |
30080 KB |
Output is correct |
19 |
Correct |
28 ms |
30080 KB |
Output is correct |
20 |
Correct |
27 ms |
30080 KB |
Output is correct |
21 |
Correct |
27 ms |
30072 KB |
Output is correct |
22 |
Correct |
27 ms |
30080 KB |
Output is correct |
23 |
Correct |
28 ms |
30072 KB |
Output is correct |
24 |
Correct |
27 ms |
30080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
29952 KB |
Output is correct |
2 |
Correct |
29 ms |
30072 KB |
Output is correct |
3 |
Correct |
27 ms |
30080 KB |
Output is correct |
4 |
Correct |
28 ms |
30076 KB |
Output is correct |
5 |
Correct |
28 ms |
30072 KB |
Output is correct |
6 |
Correct |
27 ms |
30072 KB |
Output is correct |
7 |
Correct |
28 ms |
30080 KB |
Output is correct |
8 |
Correct |
27 ms |
30072 KB |
Output is correct |
9 |
Correct |
27 ms |
30080 KB |
Output is correct |
10 |
Correct |
29 ms |
30080 KB |
Output is correct |
11 |
Correct |
29 ms |
29952 KB |
Output is correct |
12 |
Correct |
29 ms |
30072 KB |
Output is correct |
13 |
Correct |
27 ms |
30080 KB |
Output is correct |
14 |
Correct |
28 ms |
30080 KB |
Output is correct |
15 |
Correct |
29 ms |
30072 KB |
Output is correct |
16 |
Correct |
28 ms |
30072 KB |
Output is correct |
17 |
Correct |
29 ms |
30080 KB |
Output is correct |
18 |
Correct |
29 ms |
30080 KB |
Output is correct |
19 |
Correct |
28 ms |
30080 KB |
Output is correct |
20 |
Correct |
27 ms |
30080 KB |
Output is correct |
21 |
Correct |
27 ms |
30072 KB |
Output is correct |
22 |
Correct |
27 ms |
30080 KB |
Output is correct |
23 |
Correct |
28 ms |
30072 KB |
Output is correct |
24 |
Correct |
27 ms |
30080 KB |
Output is correct |
25 |
Correct |
106 ms |
35036 KB |
Output is correct |
26 |
Correct |
38 ms |
30804 KB |
Output is correct |
27 |
Correct |
137 ms |
37228 KB |
Output is correct |
28 |
Correct |
143 ms |
37432 KB |
Output is correct |
29 |
Correct |
107 ms |
35064 KB |
Output is correct |
30 |
Correct |
103 ms |
34808 KB |
Output is correct |
31 |
Correct |
120 ms |
36472 KB |
Output is correct |
32 |
Correct |
147 ms |
37240 KB |
Output is correct |
33 |
Correct |
131 ms |
36828 KB |
Output is correct |
34 |
Correct |
84 ms |
33500 KB |
Output is correct |
35 |
Correct |
141 ms |
37112 KB |
Output is correct |
36 |
Correct |
144 ms |
37368 KB |
Output is correct |
37 |
Correct |
95 ms |
33784 KB |
Output is correct |
38 |
Correct |
138 ms |
36332 KB |
Output is correct |
39 |
Correct |
43 ms |
31096 KB |
Output is correct |
40 |
Correct |
137 ms |
36220 KB |
Output is correct |
41 |
Correct |
113 ms |
34680 KB |
Output is correct |
42 |
Correct |
143 ms |
36216 KB |
Output is correct |
43 |
Correct |
65 ms |
32248 KB |
Output is correct |
44 |
Correct |
140 ms |
36328 KB |
Output is correct |
45 |
Correct |
48 ms |
31224 KB |
Output is correct |
46 |
Correct |
151 ms |
36216 KB |
Output is correct |
47 |
Correct |
59 ms |
31736 KB |
Output is correct |
48 |
Correct |
156 ms |
36456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
423 ms |
44408 KB |
Output is correct |
2 |
Correct |
476 ms |
46040 KB |
Output is correct |
3 |
Correct |
318 ms |
41100 KB |
Output is correct |
4 |
Correct |
473 ms |
46128 KB |
Output is correct |
5 |
Correct |
185 ms |
37240 KB |
Output is correct |
6 |
Correct |
470 ms |
46048 KB |
Output is correct |
7 |
Correct |
400 ms |
43968 KB |
Output is correct |
8 |
Correct |
444 ms |
46016 KB |
Output is correct |
9 |
Correct |
71 ms |
32504 KB |
Output is correct |
10 |
Correct |
433 ms |
45944 KB |
Output is correct |
11 |
Correct |
280 ms |
40004 KB |
Output is correct |
12 |
Correct |
460 ms |
46140 KB |
Output is correct |
13 |
Correct |
263 ms |
42456 KB |
Output is correct |
14 |
Correct |
261 ms |
41864 KB |
Output is correct |
15 |
Correct |
249 ms |
42488 KB |
Output is correct |
16 |
Correct |
217 ms |
43100 KB |
Output is correct |
17 |
Correct |
265 ms |
42356 KB |
Output is correct |
18 |
Correct |
251 ms |
42232 KB |
Output is correct |
19 |
Correct |
260 ms |
42064 KB |
Output is correct |
20 |
Correct |
248 ms |
42052 KB |
Output is correct |
21 |
Correct |
288 ms |
42076 KB |
Output is correct |
22 |
Correct |
266 ms |
42484 KB |
Output is correct |
23 |
Correct |
276 ms |
42108 KB |
Output is correct |
24 |
Correct |
219 ms |
42740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
29952 KB |
Output is correct |
2 |
Correct |
29 ms |
30072 KB |
Output is correct |
3 |
Correct |
27 ms |
30080 KB |
Output is correct |
4 |
Correct |
28 ms |
30076 KB |
Output is correct |
5 |
Correct |
28 ms |
30072 KB |
Output is correct |
6 |
Correct |
27 ms |
30072 KB |
Output is correct |
7 |
Correct |
28 ms |
30080 KB |
Output is correct |
8 |
Correct |
27 ms |
30072 KB |
Output is correct |
9 |
Correct |
27 ms |
30080 KB |
Output is correct |
10 |
Correct |
29 ms |
30080 KB |
Output is correct |
11 |
Correct |
29 ms |
29952 KB |
Output is correct |
12 |
Correct |
29 ms |
30072 KB |
Output is correct |
13 |
Correct |
27 ms |
30080 KB |
Output is correct |
14 |
Correct |
28 ms |
30080 KB |
Output is correct |
15 |
Correct |
29 ms |
30072 KB |
Output is correct |
16 |
Correct |
28 ms |
30072 KB |
Output is correct |
17 |
Correct |
29 ms |
30080 KB |
Output is correct |
18 |
Correct |
29 ms |
30080 KB |
Output is correct |
19 |
Correct |
28 ms |
30080 KB |
Output is correct |
20 |
Correct |
27 ms |
30080 KB |
Output is correct |
21 |
Correct |
27 ms |
30072 KB |
Output is correct |
22 |
Correct |
27 ms |
30080 KB |
Output is correct |
23 |
Correct |
28 ms |
30072 KB |
Output is correct |
24 |
Correct |
27 ms |
30080 KB |
Output is correct |
25 |
Correct |
106 ms |
35036 KB |
Output is correct |
26 |
Correct |
38 ms |
30804 KB |
Output is correct |
27 |
Correct |
137 ms |
37228 KB |
Output is correct |
28 |
Correct |
143 ms |
37432 KB |
Output is correct |
29 |
Correct |
107 ms |
35064 KB |
Output is correct |
30 |
Correct |
103 ms |
34808 KB |
Output is correct |
31 |
Correct |
120 ms |
36472 KB |
Output is correct |
32 |
Correct |
147 ms |
37240 KB |
Output is correct |
33 |
Correct |
131 ms |
36828 KB |
Output is correct |
34 |
Correct |
84 ms |
33500 KB |
Output is correct |
35 |
Correct |
141 ms |
37112 KB |
Output is correct |
36 |
Correct |
144 ms |
37368 KB |
Output is correct |
37 |
Correct |
95 ms |
33784 KB |
Output is correct |
38 |
Correct |
138 ms |
36332 KB |
Output is correct |
39 |
Correct |
43 ms |
31096 KB |
Output is correct |
40 |
Correct |
137 ms |
36220 KB |
Output is correct |
41 |
Correct |
113 ms |
34680 KB |
Output is correct |
42 |
Correct |
143 ms |
36216 KB |
Output is correct |
43 |
Correct |
65 ms |
32248 KB |
Output is correct |
44 |
Correct |
140 ms |
36328 KB |
Output is correct |
45 |
Correct |
48 ms |
31224 KB |
Output is correct |
46 |
Correct |
151 ms |
36216 KB |
Output is correct |
47 |
Correct |
59 ms |
31736 KB |
Output is correct |
48 |
Correct |
156 ms |
36456 KB |
Output is correct |
49 |
Correct |
423 ms |
44408 KB |
Output is correct |
50 |
Correct |
476 ms |
46040 KB |
Output is correct |
51 |
Correct |
318 ms |
41100 KB |
Output is correct |
52 |
Correct |
473 ms |
46128 KB |
Output is correct |
53 |
Correct |
185 ms |
37240 KB |
Output is correct |
54 |
Correct |
470 ms |
46048 KB |
Output is correct |
55 |
Correct |
400 ms |
43968 KB |
Output is correct |
56 |
Correct |
444 ms |
46016 KB |
Output is correct |
57 |
Correct |
71 ms |
32504 KB |
Output is correct |
58 |
Correct |
433 ms |
45944 KB |
Output is correct |
59 |
Correct |
280 ms |
40004 KB |
Output is correct |
60 |
Correct |
460 ms |
46140 KB |
Output is correct |
61 |
Correct |
263 ms |
42456 KB |
Output is correct |
62 |
Correct |
261 ms |
41864 KB |
Output is correct |
63 |
Correct |
249 ms |
42488 KB |
Output is correct |
64 |
Correct |
217 ms |
43100 KB |
Output is correct |
65 |
Correct |
265 ms |
42356 KB |
Output is correct |
66 |
Correct |
251 ms |
42232 KB |
Output is correct |
67 |
Correct |
260 ms |
42064 KB |
Output is correct |
68 |
Correct |
248 ms |
42052 KB |
Output is correct |
69 |
Correct |
288 ms |
42076 KB |
Output is correct |
70 |
Correct |
266 ms |
42484 KB |
Output is correct |
71 |
Correct |
276 ms |
42108 KB |
Output is correct |
72 |
Correct |
219 ms |
42740 KB |
Output is correct |
73 |
Correct |
667 ms |
52216 KB |
Output is correct |
74 |
Correct |
493 ms |
46868 KB |
Output is correct |
75 |
Correct |
607 ms |
50688 KB |
Output is correct |
76 |
Correct |
761 ms |
56244 KB |
Output is correct |
77 |
Correct |
378 ms |
44024 KB |
Output is correct |
78 |
Correct |
676 ms |
53084 KB |
Output is correct |
79 |
Correct |
726 ms |
53752 KB |
Output is correct |
80 |
Correct |
802 ms |
56184 KB |
Output is correct |
81 |
Correct |
247 ms |
40316 KB |
Output is correct |
82 |
Correct |
627 ms |
51404 KB |
Output is correct |
83 |
Correct |
539 ms |
49404 KB |
Output is correct |
84 |
Correct |
803 ms |
56024 KB |
Output is correct |
85 |
Correct |
469 ms |
48116 KB |
Output is correct |
86 |
Correct |
579 ms |
50820 KB |
Output is correct |
87 |
Correct |
314 ms |
44196 KB |
Output is correct |
88 |
Correct |
520 ms |
52216 KB |
Output is correct |
89 |
Correct |
539 ms |
49012 KB |
Output is correct |
90 |
Correct |
666 ms |
51156 KB |
Output is correct |
91 |
Correct |
381 ms |
45516 KB |
Output is correct |
92 |
Correct |
892 ms |
51108 KB |
Output is correct |
93 |
Correct |
347 ms |
43988 KB |
Output is correct |
94 |
Correct |
565 ms |
51364 KB |
Output is correct |
95 |
Correct |
347 ms |
44788 KB |
Output is correct |
96 |
Correct |
623 ms |
51932 KB |
Output is correct |