#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segTree{
ll lMin[800002];
ll rMaxLazy[800002];
ll ans[800002];
void init(int i, int l, int r){
ans[i] = -2e18, lMin[i] = 1e18, rMaxLazy[i] = -1e18;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
}
void propagate(int i, int l, int r){
if(rMaxLazy[i] == -1e18) return;
ans[i] = max(ans[i], rMaxLazy[i] - lMin[i]);
if(l!=r){
rMaxLazy[i*2] = max(rMaxLazy[i*2], rMaxLazy[i]);
rMaxLazy[i*2+1] = max(rMaxLazy[i*2+1], rMaxLazy[i]);
}
rMaxLazy[i] = -1e18;
}
void updateL(int i, int l, int r, int x, ll v){
propagate(i, l, r);
if(l==r){
lMin[i] = v;
return;
}
int m = (l+r)>>1;
if(x<=m) updateL(i*2, l, m, x, v);
else updateL(i*2+1, m+1, r, x, v);
lMin[i] = min(lMin[i*2], lMin[i*2+1]);
}
void updateR(int i, int l, int r, int s, int e, ll v){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
rMaxLazy[i] = v;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
updateR(i*2, l, m, s, e, v);
updateR(i*2+1, m+1, r, s, e, v);
ans[i] = max(ans[i*2], ans[i*2+1]);
}
ll query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return -1;
if(s<=l && r<=e) return ans[i];
int m = (l+r)>>1;
return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
} tree;
int n, q;
ll h[200002];
int a[200002], b[200002];
ll ans[200002];
int l[200002], r[200002];
vector<pair<int, int> > query[200002]; /// (쿼리 번호, l)
vector<pair<int, ll> > update[200002];
void solve(){
for(int i=1; i<=n; i++){
query[i].clear();
update[i].clear();
}
for(int i=1; i<=q; i++){
query[r[i]].push_back(make_pair(i, l[i]));
}
for(int i=1; i<=n; i++){
update[min(i+a[i], n+1)].push_back(make_pair(i, h[i]));
update[min(i+b[i]+1, n+1)].push_back(make_pair(i, 1e18));
}
tree.init(1, 1, n);
for(int i=1; i<=n; i++){
for(auto p: update[i]){
tree.updateL(1, 1, n, p.first, p.second);
}
tree.updateR(1, 1, n, i-b[i], i-a[i], h[i]);
for(auto p: query[i]){
ans[p.first] = max(ans[p.first], tree.query(1, 1, n, p.second, i));
}
}
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%lld %d %d", &h[i], &a[i], &b[i]);
}
scanf("%d", &q);
for(int i=1; i<=q; i++){
scanf("%d %d", &l[i], &r[i]);
ans[i] = -1;
}
solve();
for(int i=1; i<=n; i++) h[i] = 1000000001 - h[i];
solve();
for(int i=1; i<=q; i++) printf("%lld\n", ans[i]);
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:99:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
antennas.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf("%lld %d %d", &h[i], &a[i], &b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
antennas.cpp:105:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | scanf("%d %d", &l[i], &r[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
6 ms |
9700 KB |
Output is correct |
3 |
Correct |
7 ms |
9704 KB |
Output is correct |
4 |
Correct |
6 ms |
9812 KB |
Output is correct |
5 |
Correct |
6 ms |
9684 KB |
Output is correct |
6 |
Correct |
6 ms |
9812 KB |
Output is correct |
7 |
Correct |
6 ms |
9812 KB |
Output is correct |
8 |
Correct |
6 ms |
9836 KB |
Output is correct |
9 |
Correct |
7 ms |
9728 KB |
Output is correct |
10 |
Correct |
6 ms |
9812 KB |
Output is correct |
11 |
Correct |
6 ms |
9684 KB |
Output is correct |
12 |
Correct |
6 ms |
9812 KB |
Output is correct |
13 |
Correct |
5 ms |
9812 KB |
Output is correct |
14 |
Correct |
7 ms |
9808 KB |
Output is correct |
15 |
Correct |
6 ms |
9704 KB |
Output is correct |
16 |
Correct |
6 ms |
9940 KB |
Output is correct |
17 |
Correct |
6 ms |
9716 KB |
Output is correct |
18 |
Correct |
6 ms |
9804 KB |
Output is correct |
19 |
Correct |
6 ms |
9684 KB |
Output is correct |
20 |
Correct |
5 ms |
9684 KB |
Output is correct |
21 |
Correct |
6 ms |
9708 KB |
Output is correct |
22 |
Correct |
6 ms |
9704 KB |
Output is correct |
23 |
Correct |
6 ms |
9684 KB |
Output is correct |
24 |
Correct |
6 ms |
9708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
6 ms |
9700 KB |
Output is correct |
3 |
Correct |
7 ms |
9704 KB |
Output is correct |
4 |
Correct |
6 ms |
9812 KB |
Output is correct |
5 |
Correct |
6 ms |
9684 KB |
Output is correct |
6 |
Correct |
6 ms |
9812 KB |
Output is correct |
7 |
Correct |
6 ms |
9812 KB |
Output is correct |
8 |
Correct |
6 ms |
9836 KB |
Output is correct |
9 |
Correct |
7 ms |
9728 KB |
Output is correct |
10 |
Correct |
6 ms |
9812 KB |
Output is correct |
11 |
Correct |
6 ms |
9684 KB |
Output is correct |
12 |
Correct |
6 ms |
9812 KB |
Output is correct |
13 |
Correct |
5 ms |
9812 KB |
Output is correct |
14 |
Correct |
7 ms |
9808 KB |
Output is correct |
15 |
Correct |
6 ms |
9704 KB |
Output is correct |
16 |
Correct |
6 ms |
9940 KB |
Output is correct |
17 |
Correct |
6 ms |
9716 KB |
Output is correct |
18 |
Correct |
6 ms |
9804 KB |
Output is correct |
19 |
Correct |
6 ms |
9684 KB |
Output is correct |
20 |
Correct |
5 ms |
9684 KB |
Output is correct |
21 |
Correct |
6 ms |
9708 KB |
Output is correct |
22 |
Correct |
6 ms |
9704 KB |
Output is correct |
23 |
Correct |
6 ms |
9684 KB |
Output is correct |
24 |
Correct |
6 ms |
9708 KB |
Output is correct |
25 |
Correct |
98 ms |
16424 KB |
Output is correct |
26 |
Correct |
19 ms |
10716 KB |
Output is correct |
27 |
Correct |
143 ms |
18996 KB |
Output is correct |
28 |
Correct |
143 ms |
19108 KB |
Output is correct |
29 |
Correct |
95 ms |
16336 KB |
Output is correct |
30 |
Correct |
99 ms |
16252 KB |
Output is correct |
31 |
Correct |
110 ms |
18112 KB |
Output is correct |
32 |
Correct |
144 ms |
19020 KB |
Output is correct |
33 |
Correct |
128 ms |
18596 KB |
Output is correct |
34 |
Correct |
80 ms |
14412 KB |
Output is correct |
35 |
Correct |
137 ms |
18892 KB |
Output is correct |
36 |
Correct |
150 ms |
19004 KB |
Output is correct |
37 |
Correct |
83 ms |
14928 KB |
Output is correct |
38 |
Correct |
143 ms |
17952 KB |
Output is correct |
39 |
Correct |
27 ms |
11320 KB |
Output is correct |
40 |
Correct |
144 ms |
17996 KB |
Output is correct |
41 |
Correct |
107 ms |
16012 KB |
Output is correct |
42 |
Correct |
134 ms |
18068 KB |
Output is correct |
43 |
Correct |
49 ms |
12616 KB |
Output is correct |
44 |
Correct |
139 ms |
18060 KB |
Output is correct |
45 |
Correct |
30 ms |
11328 KB |
Output is correct |
46 |
Correct |
140 ms |
18076 KB |
Output is correct |
47 |
Correct |
40 ms |
12112 KB |
Output is correct |
48 |
Correct |
146 ms |
18024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
335 ms |
36656 KB |
Output is correct |
2 |
Correct |
327 ms |
37372 KB |
Output is correct |
3 |
Correct |
218 ms |
35224 KB |
Output is correct |
4 |
Correct |
324 ms |
37348 KB |
Output is correct |
5 |
Correct |
132 ms |
23352 KB |
Output is correct |
6 |
Correct |
329 ms |
37296 KB |
Output is correct |
7 |
Correct |
285 ms |
36376 KB |
Output is correct |
8 |
Correct |
327 ms |
38984 KB |
Output is correct |
9 |
Correct |
44 ms |
15104 KB |
Output is correct |
10 |
Correct |
334 ms |
39092 KB |
Output is correct |
11 |
Correct |
194 ms |
30280 KB |
Output is correct |
12 |
Correct |
324 ms |
39016 KB |
Output is correct |
13 |
Correct |
197 ms |
39308 KB |
Output is correct |
14 |
Correct |
191 ms |
38360 KB |
Output is correct |
15 |
Correct |
180 ms |
38528 KB |
Output is correct |
16 |
Correct |
148 ms |
39228 KB |
Output is correct |
17 |
Correct |
203 ms |
39616 KB |
Output is correct |
18 |
Correct |
177 ms |
39132 KB |
Output is correct |
19 |
Correct |
186 ms |
38604 KB |
Output is correct |
20 |
Correct |
182 ms |
38436 KB |
Output is correct |
21 |
Correct |
186 ms |
37480 KB |
Output is correct |
22 |
Correct |
187 ms |
38064 KB |
Output is correct |
23 |
Correct |
184 ms |
38856 KB |
Output is correct |
24 |
Correct |
158 ms |
38852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9684 KB |
Output is correct |
2 |
Correct |
6 ms |
9700 KB |
Output is correct |
3 |
Correct |
7 ms |
9704 KB |
Output is correct |
4 |
Correct |
6 ms |
9812 KB |
Output is correct |
5 |
Correct |
6 ms |
9684 KB |
Output is correct |
6 |
Correct |
6 ms |
9812 KB |
Output is correct |
7 |
Correct |
6 ms |
9812 KB |
Output is correct |
8 |
Correct |
6 ms |
9836 KB |
Output is correct |
9 |
Correct |
7 ms |
9728 KB |
Output is correct |
10 |
Correct |
6 ms |
9812 KB |
Output is correct |
11 |
Correct |
6 ms |
9684 KB |
Output is correct |
12 |
Correct |
6 ms |
9812 KB |
Output is correct |
13 |
Correct |
5 ms |
9812 KB |
Output is correct |
14 |
Correct |
7 ms |
9808 KB |
Output is correct |
15 |
Correct |
6 ms |
9704 KB |
Output is correct |
16 |
Correct |
6 ms |
9940 KB |
Output is correct |
17 |
Correct |
6 ms |
9716 KB |
Output is correct |
18 |
Correct |
6 ms |
9804 KB |
Output is correct |
19 |
Correct |
6 ms |
9684 KB |
Output is correct |
20 |
Correct |
5 ms |
9684 KB |
Output is correct |
21 |
Correct |
6 ms |
9708 KB |
Output is correct |
22 |
Correct |
6 ms |
9704 KB |
Output is correct |
23 |
Correct |
6 ms |
9684 KB |
Output is correct |
24 |
Correct |
6 ms |
9708 KB |
Output is correct |
25 |
Correct |
98 ms |
16424 KB |
Output is correct |
26 |
Correct |
19 ms |
10716 KB |
Output is correct |
27 |
Correct |
143 ms |
18996 KB |
Output is correct |
28 |
Correct |
143 ms |
19108 KB |
Output is correct |
29 |
Correct |
95 ms |
16336 KB |
Output is correct |
30 |
Correct |
99 ms |
16252 KB |
Output is correct |
31 |
Correct |
110 ms |
18112 KB |
Output is correct |
32 |
Correct |
144 ms |
19020 KB |
Output is correct |
33 |
Correct |
128 ms |
18596 KB |
Output is correct |
34 |
Correct |
80 ms |
14412 KB |
Output is correct |
35 |
Correct |
137 ms |
18892 KB |
Output is correct |
36 |
Correct |
150 ms |
19004 KB |
Output is correct |
37 |
Correct |
83 ms |
14928 KB |
Output is correct |
38 |
Correct |
143 ms |
17952 KB |
Output is correct |
39 |
Correct |
27 ms |
11320 KB |
Output is correct |
40 |
Correct |
144 ms |
17996 KB |
Output is correct |
41 |
Correct |
107 ms |
16012 KB |
Output is correct |
42 |
Correct |
134 ms |
18068 KB |
Output is correct |
43 |
Correct |
49 ms |
12616 KB |
Output is correct |
44 |
Correct |
139 ms |
18060 KB |
Output is correct |
45 |
Correct |
30 ms |
11328 KB |
Output is correct |
46 |
Correct |
140 ms |
18076 KB |
Output is correct |
47 |
Correct |
40 ms |
12112 KB |
Output is correct |
48 |
Correct |
146 ms |
18024 KB |
Output is correct |
49 |
Correct |
335 ms |
36656 KB |
Output is correct |
50 |
Correct |
327 ms |
37372 KB |
Output is correct |
51 |
Correct |
218 ms |
35224 KB |
Output is correct |
52 |
Correct |
324 ms |
37348 KB |
Output is correct |
53 |
Correct |
132 ms |
23352 KB |
Output is correct |
54 |
Correct |
329 ms |
37296 KB |
Output is correct |
55 |
Correct |
285 ms |
36376 KB |
Output is correct |
56 |
Correct |
327 ms |
38984 KB |
Output is correct |
57 |
Correct |
44 ms |
15104 KB |
Output is correct |
58 |
Correct |
334 ms |
39092 KB |
Output is correct |
59 |
Correct |
194 ms |
30280 KB |
Output is correct |
60 |
Correct |
324 ms |
39016 KB |
Output is correct |
61 |
Correct |
197 ms |
39308 KB |
Output is correct |
62 |
Correct |
191 ms |
38360 KB |
Output is correct |
63 |
Correct |
180 ms |
38528 KB |
Output is correct |
64 |
Correct |
148 ms |
39228 KB |
Output is correct |
65 |
Correct |
203 ms |
39616 KB |
Output is correct |
66 |
Correct |
177 ms |
39132 KB |
Output is correct |
67 |
Correct |
186 ms |
38604 KB |
Output is correct |
68 |
Correct |
182 ms |
38436 KB |
Output is correct |
69 |
Correct |
186 ms |
37480 KB |
Output is correct |
70 |
Correct |
187 ms |
38064 KB |
Output is correct |
71 |
Correct |
184 ms |
38856 KB |
Output is correct |
72 |
Correct |
158 ms |
38852 KB |
Output is correct |
73 |
Correct |
579 ms |
43884 KB |
Output is correct |
74 |
Correct |
374 ms |
39668 KB |
Output is correct |
75 |
Correct |
527 ms |
43400 KB |
Output is correct |
76 |
Correct |
681 ms |
47520 KB |
Output is correct |
77 |
Correct |
348 ms |
30768 KB |
Output is correct |
78 |
Correct |
550 ms |
44912 KB |
Output is correct |
79 |
Correct |
613 ms |
45444 KB |
Output is correct |
80 |
Correct |
669 ms |
47516 KB |
Output is correct |
81 |
Correct |
249 ms |
22672 KB |
Output is correct |
82 |
Correct |
500 ms |
43300 KB |
Output is correct |
83 |
Correct |
486 ms |
36756 KB |
Output is correct |
84 |
Correct |
671 ms |
47516 KB |
Output is correct |
85 |
Correct |
378 ms |
43472 KB |
Output is correct |
86 |
Correct |
470 ms |
45248 KB |
Output is correct |
87 |
Correct |
235 ms |
39664 KB |
Output is correct |
88 |
Correct |
437 ms |
46184 KB |
Output is correct |
89 |
Correct |
425 ms |
44640 KB |
Output is correct |
90 |
Correct |
475 ms |
45992 KB |
Output is correct |
91 |
Correct |
300 ms |
41268 KB |
Output is correct |
92 |
Correct |
498 ms |
45320 KB |
Output is correct |
93 |
Correct |
236 ms |
39072 KB |
Output is correct |
94 |
Correct |
490 ms |
44964 KB |
Output is correct |
95 |
Correct |
269 ms |
41056 KB |
Output is correct |
96 |
Correct |
447 ms |
45764 KB |
Output is correct |