#include <bits/stdc++.h>
using namespace std;
struct segtree{
int T[606060], L[606060], C[606060];
void spread(int p)
{
L[p << 1] = max(L[p << 1], L[p]);
T[p << 1] = max(T[p << 1], L[p << 1] - C[p << 1]);
L[p << 1 | 1] = max(L[p << 1 | 1], L[p]);
T[p << 1 | 1] = max(T[p << 1 | 1], L[p << 1 | 1] - C[p << 1 | 1]);
L[p] = 0;
}
void update(int p)
{
C[p] = min(C[p << 1], C[p << 1 | 1]);
T[p] = max(T[p << 1], T[p << 1 | 1]);
}
void init(int p, int s, int e)
{
T[p] = -1e9, L[p] = 0, C[p] = 2e9;
if(s != e){
init(p << 1, s, s + e >> 1);
init(p << 1 | 1, (s + e >> 1) + 1, e);
}
}
void update1(int p, int s, int e, int v, int c)
{
if(s == e) L[p] = 0, C[p] = c;
else{
spread(p);
if(v <= (s + e >> 1)) update1(p << 1, s, s + e >> 1, v, c);
else update1(p << 1 | 1, (s + e >> 1) + 1, e, v, c);
update(p);
}
}
void update2(int p, int s, int e, int l, int r, int c)
{
if(e < l || r < s) return;
else if(l <= s && e <= r){
L[p] = max(L[p], c);
T[p] = max(T[p], L[p] - C[p]);
return;
}
spread(p);
update2(p << 1, s, s + e >> 1, l, r, c);
update2(p << 1 | 1, (s + e >> 1) + 1, e, l, r, c);
update(p);
}
int getmax(int p, int s, int e, int l, int r)
{
if(e < l || r < s) return -1e9;
else if(l <= s && e <= r) return T[p];
spread(p);
int ret = getmax(p << 1, s, s + e >> 1, l, r);
ret = max(ret, getmax(p << 1 | 1, (s + e >> 1) + 1, e, l, r));
update(p);
return ret;
}
};
segtree T;
vector <int> V[202020], Q[202020];
int H[202020], A[201010], B[202020];
int L[202020], R[202020], X[202020];
int n, q;
void f()
{
int i;
T.init(1, 1, n);
for(i=1; i<=n; i++){
V[i].clear(); Q[i].clear();
}
for(i=1; i<=q; i++){
Q[R[i]].push_back(i);
}
for(i=1; i<=n; i++){
if(i + A[i] <= n) V[i + A[i]].push_back(i);
if(i + B[i] < n) V[i + B[i] + 1].push_back(-i);
for(int &t: V[i]){
if(t > 0) T.update1(1, 1, n, t, H[t]);
else T.update1(1, 1, n, -t, 2e9);
}
if(i - A[i] >= 1){
T.update2(1, 1, n, max(1, i - B[i]), i - A[i], H[i]);
}
for(int &t: Q[i]){
X[t] = max(X[t], T.getmax(1, 1, n, L[t], i));
}
}
}
int main()
{
int i;
scanf("%d", &n);
for(i=1; i<=n; i++){
scanf("%d%d%d", H + i, A + i, B + i);
}
scanf("%d", &q);
for(i=1; i<=q; i++){
scanf("%d%d", L + i, R + i);
X[i] = -1;
}
f();
reverse(H + 1, H + n + 1);
reverse(A + 1, A + n + 1);
reverse(B + 1, B + n + 1);
for(i=1; i<=q; i++){
L[i] = n + 1 - L[i];
R[i] = n + 1 - R[i];
swap(L[i], R[i]);
}
f();
for(i=1; i<=q; i++){
printf("%d\n", X[i]);
}
return 0;
}
Compilation message
antennas.cpp: In member function 'void segtree::init(int, int, int)':
antennas.cpp:27:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
init(p << 1, s, s + e >> 1);
~~^~~
antennas.cpp:28:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
init(p << 1 | 1, (s + e >> 1) + 1, e);
~~^~~
antennas.cpp: In member function 'void segtree::update1(int, int, int, int, int)':
antennas.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
if(v <= (s + e >> 1)) update1(p << 1, s, s + e >> 1, v, c);
~~^~~
antennas.cpp:37:47: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
if(v <= (s + e >> 1)) update1(p << 1, s, s + e >> 1, v, c);
~~^~~
antennas.cpp:38:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
else update1(p << 1 | 1, (s + e >> 1) + 1, e, v, c);
~~^~~
antennas.cpp: In member function 'void segtree::update2(int, int, int, int, int, int)':
antennas.cpp:53:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
update2(p << 1, s, s + e >> 1, l, r, c);
~~^~~
antennas.cpp:54:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
update2(p << 1 | 1, (s + e >> 1) + 1, e, l, r, c);
~~^~~
antennas.cpp: In member function 'int segtree::getmax(int, int, int, int, int)':
antennas.cpp:64:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int ret = getmax(p << 1, s, s + e >> 1, l, r);
~~^~~
antennas.cpp:65:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
ret = max(ret, getmax(p << 1 | 1, (s + e >> 1) + 1, e, l, r));
~~^~~
antennas.cpp: In function 'int main()':
antennas.cpp:115:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
antennas.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", H + i, A + i, B + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
antennas.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", L + i, R + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9848 KB |
Output is correct |
2 |
Correct |
10 ms |
9848 KB |
Output is correct |
3 |
Correct |
11 ms |
9976 KB |
Output is correct |
4 |
Correct |
11 ms |
9852 KB |
Output is correct |
5 |
Correct |
10 ms |
9820 KB |
Output is correct |
6 |
Correct |
10 ms |
9848 KB |
Output is correct |
7 |
Correct |
11 ms |
9848 KB |
Output is correct |
8 |
Correct |
11 ms |
9976 KB |
Output is correct |
9 |
Correct |
11 ms |
9848 KB |
Output is correct |
10 |
Correct |
10 ms |
9848 KB |
Output is correct |
11 |
Correct |
10 ms |
9848 KB |
Output is correct |
12 |
Correct |
11 ms |
9848 KB |
Output is correct |
13 |
Correct |
10 ms |
9848 KB |
Output is correct |
14 |
Correct |
11 ms |
9976 KB |
Output is correct |
15 |
Correct |
11 ms |
9848 KB |
Output is correct |
16 |
Correct |
13 ms |
9848 KB |
Output is correct |
17 |
Correct |
13 ms |
9948 KB |
Output is correct |
18 |
Correct |
13 ms |
9976 KB |
Output is correct |
19 |
Correct |
13 ms |
9848 KB |
Output is correct |
20 |
Correct |
13 ms |
9848 KB |
Output is correct |
21 |
Correct |
13 ms |
9848 KB |
Output is correct |
22 |
Correct |
13 ms |
9848 KB |
Output is correct |
23 |
Correct |
10 ms |
9848 KB |
Output is correct |
24 |
Correct |
10 ms |
9848 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9848 KB |
Output is correct |
2 |
Correct |
10 ms |
9848 KB |
Output is correct |
3 |
Correct |
11 ms |
9976 KB |
Output is correct |
4 |
Correct |
11 ms |
9852 KB |
Output is correct |
5 |
Correct |
10 ms |
9820 KB |
Output is correct |
6 |
Correct |
10 ms |
9848 KB |
Output is correct |
7 |
Correct |
11 ms |
9848 KB |
Output is correct |
8 |
Correct |
11 ms |
9976 KB |
Output is correct |
9 |
Correct |
11 ms |
9848 KB |
Output is correct |
10 |
Correct |
10 ms |
9848 KB |
Output is correct |
11 |
Correct |
10 ms |
9848 KB |
Output is correct |
12 |
Correct |
11 ms |
9848 KB |
Output is correct |
13 |
Correct |
10 ms |
9848 KB |
Output is correct |
14 |
Correct |
11 ms |
9976 KB |
Output is correct |
15 |
Correct |
11 ms |
9848 KB |
Output is correct |
16 |
Correct |
13 ms |
9848 KB |
Output is correct |
17 |
Correct |
13 ms |
9948 KB |
Output is correct |
18 |
Correct |
13 ms |
9976 KB |
Output is correct |
19 |
Correct |
13 ms |
9848 KB |
Output is correct |
20 |
Correct |
13 ms |
9848 KB |
Output is correct |
21 |
Correct |
13 ms |
9848 KB |
Output is correct |
22 |
Correct |
13 ms |
9848 KB |
Output is correct |
23 |
Correct |
10 ms |
9848 KB |
Output is correct |
24 |
Correct |
10 ms |
9848 KB |
Output is correct |
25 |
Correct |
131 ms |
15324 KB |
Output is correct |
26 |
Correct |
27 ms |
10664 KB |
Output is correct |
27 |
Correct |
185 ms |
17580 KB |
Output is correct |
28 |
Correct |
189 ms |
17528 KB |
Output is correct |
29 |
Correct |
130 ms |
15352 KB |
Output is correct |
30 |
Correct |
132 ms |
15048 KB |
Output is correct |
31 |
Correct |
146 ms |
16704 KB |
Output is correct |
32 |
Correct |
192 ms |
17528 KB |
Output is correct |
33 |
Correct |
175 ms |
17116 KB |
Output is correct |
34 |
Correct |
99 ms |
13560 KB |
Output is correct |
35 |
Correct |
186 ms |
17656 KB |
Output is correct |
36 |
Correct |
193 ms |
17528 KB |
Output is correct |
37 |
Correct |
113 ms |
13816 KB |
Output is correct |
38 |
Correct |
187 ms |
16620 KB |
Output is correct |
39 |
Correct |
36 ms |
10872 KB |
Output is correct |
40 |
Correct |
186 ms |
16504 KB |
Output is correct |
41 |
Correct |
137 ms |
14840 KB |
Output is correct |
42 |
Correct |
184 ms |
16500 KB |
Output is correct |
43 |
Correct |
69 ms |
12152 KB |
Output is correct |
44 |
Correct |
188 ms |
16512 KB |
Output is correct |
45 |
Correct |
41 ms |
11128 KB |
Output is correct |
46 |
Correct |
185 ms |
16632 KB |
Output is correct |
47 |
Correct |
56 ms |
11640 KB |
Output is correct |
48 |
Correct |
183 ms |
16632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
345 ms |
25892 KB |
Output is correct |
2 |
Correct |
382 ms |
27000 KB |
Output is correct |
3 |
Correct |
259 ms |
23672 KB |
Output is correct |
4 |
Correct |
410 ms |
27144 KB |
Output is correct |
5 |
Correct |
169 ms |
18048 KB |
Output is correct |
6 |
Correct |
393 ms |
26988 KB |
Output is correct |
7 |
Correct |
338 ms |
25596 KB |
Output is correct |
8 |
Correct |
404 ms |
27000 KB |
Output is correct |
9 |
Correct |
54 ms |
12284 KB |
Output is correct |
10 |
Correct |
397 ms |
26960 KB |
Output is correct |
11 |
Correct |
223 ms |
19832 KB |
Output is correct |
12 |
Correct |
397 ms |
27000 KB |
Output is correct |
13 |
Correct |
259 ms |
26100 KB |
Output is correct |
14 |
Correct |
241 ms |
25624 KB |
Output is correct |
15 |
Correct |
242 ms |
24904 KB |
Output is correct |
16 |
Correct |
221 ms |
24984 KB |
Output is correct |
17 |
Correct |
267 ms |
26484 KB |
Output is correct |
18 |
Correct |
245 ms |
25504 KB |
Output is correct |
19 |
Correct |
268 ms |
25480 KB |
Output is correct |
20 |
Correct |
254 ms |
25460 KB |
Output is correct |
21 |
Correct |
242 ms |
25652 KB |
Output is correct |
22 |
Correct |
248 ms |
25716 KB |
Output is correct |
23 |
Correct |
249 ms |
25720 KB |
Output is correct |
24 |
Correct |
223 ms |
24720 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9848 KB |
Output is correct |
2 |
Correct |
10 ms |
9848 KB |
Output is correct |
3 |
Correct |
11 ms |
9976 KB |
Output is correct |
4 |
Correct |
11 ms |
9852 KB |
Output is correct |
5 |
Correct |
10 ms |
9820 KB |
Output is correct |
6 |
Correct |
10 ms |
9848 KB |
Output is correct |
7 |
Correct |
11 ms |
9848 KB |
Output is correct |
8 |
Correct |
11 ms |
9976 KB |
Output is correct |
9 |
Correct |
11 ms |
9848 KB |
Output is correct |
10 |
Correct |
10 ms |
9848 KB |
Output is correct |
11 |
Correct |
10 ms |
9848 KB |
Output is correct |
12 |
Correct |
11 ms |
9848 KB |
Output is correct |
13 |
Correct |
10 ms |
9848 KB |
Output is correct |
14 |
Correct |
11 ms |
9976 KB |
Output is correct |
15 |
Correct |
11 ms |
9848 KB |
Output is correct |
16 |
Correct |
13 ms |
9848 KB |
Output is correct |
17 |
Correct |
13 ms |
9948 KB |
Output is correct |
18 |
Correct |
13 ms |
9976 KB |
Output is correct |
19 |
Correct |
13 ms |
9848 KB |
Output is correct |
20 |
Correct |
13 ms |
9848 KB |
Output is correct |
21 |
Correct |
13 ms |
9848 KB |
Output is correct |
22 |
Correct |
13 ms |
9848 KB |
Output is correct |
23 |
Correct |
10 ms |
9848 KB |
Output is correct |
24 |
Correct |
10 ms |
9848 KB |
Output is correct |
25 |
Correct |
131 ms |
15324 KB |
Output is correct |
26 |
Correct |
27 ms |
10664 KB |
Output is correct |
27 |
Correct |
185 ms |
17580 KB |
Output is correct |
28 |
Correct |
189 ms |
17528 KB |
Output is correct |
29 |
Correct |
130 ms |
15352 KB |
Output is correct |
30 |
Correct |
132 ms |
15048 KB |
Output is correct |
31 |
Correct |
146 ms |
16704 KB |
Output is correct |
32 |
Correct |
192 ms |
17528 KB |
Output is correct |
33 |
Correct |
175 ms |
17116 KB |
Output is correct |
34 |
Correct |
99 ms |
13560 KB |
Output is correct |
35 |
Correct |
186 ms |
17656 KB |
Output is correct |
36 |
Correct |
193 ms |
17528 KB |
Output is correct |
37 |
Correct |
113 ms |
13816 KB |
Output is correct |
38 |
Correct |
187 ms |
16620 KB |
Output is correct |
39 |
Correct |
36 ms |
10872 KB |
Output is correct |
40 |
Correct |
186 ms |
16504 KB |
Output is correct |
41 |
Correct |
137 ms |
14840 KB |
Output is correct |
42 |
Correct |
184 ms |
16500 KB |
Output is correct |
43 |
Correct |
69 ms |
12152 KB |
Output is correct |
44 |
Correct |
188 ms |
16512 KB |
Output is correct |
45 |
Correct |
41 ms |
11128 KB |
Output is correct |
46 |
Correct |
185 ms |
16632 KB |
Output is correct |
47 |
Correct |
56 ms |
11640 KB |
Output is correct |
48 |
Correct |
183 ms |
16632 KB |
Output is correct |
49 |
Correct |
345 ms |
25892 KB |
Output is correct |
50 |
Correct |
382 ms |
27000 KB |
Output is correct |
51 |
Correct |
259 ms |
23672 KB |
Output is correct |
52 |
Correct |
410 ms |
27144 KB |
Output is correct |
53 |
Correct |
169 ms |
18048 KB |
Output is correct |
54 |
Correct |
393 ms |
26988 KB |
Output is correct |
55 |
Correct |
338 ms |
25596 KB |
Output is correct |
56 |
Correct |
404 ms |
27000 KB |
Output is correct |
57 |
Correct |
54 ms |
12284 KB |
Output is correct |
58 |
Correct |
397 ms |
26960 KB |
Output is correct |
59 |
Correct |
223 ms |
19832 KB |
Output is correct |
60 |
Correct |
397 ms |
27000 KB |
Output is correct |
61 |
Correct |
259 ms |
26100 KB |
Output is correct |
62 |
Correct |
241 ms |
25624 KB |
Output is correct |
63 |
Correct |
242 ms |
24904 KB |
Output is correct |
64 |
Correct |
221 ms |
24984 KB |
Output is correct |
65 |
Correct |
267 ms |
26484 KB |
Output is correct |
66 |
Correct |
245 ms |
25504 KB |
Output is correct |
67 |
Correct |
268 ms |
25480 KB |
Output is correct |
68 |
Correct |
254 ms |
25460 KB |
Output is correct |
69 |
Correct |
242 ms |
25652 KB |
Output is correct |
70 |
Correct |
248 ms |
25716 KB |
Output is correct |
71 |
Correct |
249 ms |
25720 KB |
Output is correct |
72 |
Correct |
223 ms |
24720 KB |
Output is correct |
73 |
Correct |
684 ms |
35348 KB |
Output is correct |
74 |
Correct |
436 ms |
28408 KB |
Output is correct |
75 |
Correct |
646 ms |
34840 KB |
Output is correct |
76 |
Correct |
860 ms |
39140 KB |
Output is correct |
77 |
Correct |
501 ms |
25720 KB |
Output is correct |
78 |
Correct |
729 ms |
36024 KB |
Output is correct |
79 |
Correct |
775 ms |
37300 KB |
Output is correct |
80 |
Correct |
850 ms |
39432 KB |
Output is correct |
81 |
Correct |
331 ms |
20728 KB |
Output is correct |
82 |
Correct |
634 ms |
34296 KB |
Output is correct |
83 |
Correct |
615 ms |
30440 KB |
Output is correct |
84 |
Correct |
855 ms |
39288 KB |
Output is correct |
85 |
Correct |
519 ms |
33356 KB |
Output is correct |
86 |
Correct |
676 ms |
36792 KB |
Output is correct |
87 |
Correct |
304 ms |
27124 KB |
Output is correct |
88 |
Correct |
657 ms |
36012 KB |
Output is correct |
89 |
Correct |
577 ms |
35188 KB |
Output is correct |
90 |
Correct |
674 ms |
36316 KB |
Output is correct |
91 |
Correct |
395 ms |
30312 KB |
Output is correct |
92 |
Correct |
665 ms |
36536 KB |
Output is correct |
93 |
Correct |
310 ms |
28532 KB |
Output is correct |
94 |
Correct |
670 ms |
36832 KB |
Output is correct |
95 |
Correct |
390 ms |
29668 KB |
Output is correct |
96 |
Correct |
796 ms |
35700 KB |
Output is correct |