#include<bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define all(s) s.begin(), s.end()
using namespace std;
const int N = 2e5 + 5;
int n, c[N], a[N], b[N], ans[N], L[N], R[N], q;
struct tree{
int val, sc, must;
tree(){
val = -1;
sc = -1e9;
must = 1e9;
}
};
tree t[N * 4];
void push (int v, int tl, int tr){
t[v].val = max( t[v].val, t[v].sc - t[v].must );
if (tl != tr){
t[v + v].must = min( t[v + v].must, t[v].must );
t[v + v + 1].must = min( t[v + v + 1].must, t[v].must );
}
t[v].must = 1e9;
}
void update2 (int pos, int val, int v = 1, int tl = 1, int tr = n)
{
push(v, tl, tr);
if (tl == tr){
t[v].sc = val;
}
else{
int tm = (tl + tr) >> 1;
if (pos <= tm)
update2( pos, val, v + v, tl, tm );
else
update2( pos, val, v + v + 1, tm + 1, tr );
t[v].sc = max(t[v + v].sc, t[v + v + 1].sc);
}
}
void update1 (int l, int r, int val, int v = 1, int tl = 1, int tr = n)
{
push(v, tl, tr);
if (l > r || tl > r || l > tr) return;
if (l <= tl && tr <= r){
t[v].must = min( t[v].must, val );
push(v, tl, tr);
return;
}
int tm = (tl + tr) >> 1;
update1(l, r, val, v + v, tl, tm);
update1(l, r, val, v + v + 1, tm + 1, tr);
t[v].val = max( t[v + v].val, t[v + v + 1].val );
}
int get (int l, int r, int v = 1, int tl = 1, int tr = n)
{
if (tl > r || l > tr) return -1;
push(v, tl, tr);
if (l <= tl && tr <= r)
return t[v].val;
int tm = (tl + tr) >> 1;
return max( get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr) );
}
vector <int> add[N], del[N], calc[N];
void solve (){
for (int i = 1; i <= n; i++)
add[i].clear(),
del[i].clear(),
calc[i].clear();
for (int i = 1; i <= q; i++){
calc[ R[i] ].pb(i);
}
for (int i = 1; i <= n; i++){
for (auto it : add[i]){
update2( it, c[it] );
}
for (auto it : del[i]){
update2( it, -1e9 );
}
update1( max(1, i - b[i]), i - a[i], c[i] );
if (i + a[i] <= n)
add[ i + a[i] ].pb( i );
if (i + b[i] + 1 <= n)
del[ i + b[i] + 1 ].pb( i );
for (auto it : calc[i]){
ans[it] = max( ans[it], get( L[it], i ) );
}
}
for (int i = 0; i < 4 * N; i++)
t[i] = tree();
}
main(){
memset(ans, -1, sizeof(ans));
cin >> n;
for (int i = 1; i <= n; i++){
scanf("%d%d%d", &c[i], &a[i], &b[i]);
}
cin >> q;
for (int i = 1; i <= q; i++){
scanf("%d%d", &L[i], &R[i]);
}
solve();
for (int i = 1; i <= q; i++){
L[i] = n - L[i] + 1;
R[i] = n - R[i] + 1;
swap(L[i], R[i]);
}
reverse(c + 1, c + n + 1);
reverse(a + 1, a + n + 1);
reverse(b + 1, b + n + 1);
solve();
for (int i = 1; i <= q; i++)
printf("%d\n", ans[i]);
}
/**
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5
**/
Compilation message
antennas.cpp:125:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
antennas.cpp: In function 'int main()':
antennas.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &c[i], &a[i], &b[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:135:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &L[i], &R[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
24576 KB |
Output is correct |
2 |
Correct |
28 ms |
24568 KB |
Output is correct |
3 |
Correct |
28 ms |
24704 KB |
Output is correct |
4 |
Correct |
32 ms |
24704 KB |
Output is correct |
5 |
Correct |
29 ms |
24676 KB |
Output is correct |
6 |
Correct |
31 ms |
24732 KB |
Output is correct |
7 |
Correct |
34 ms |
24568 KB |
Output is correct |
8 |
Correct |
28 ms |
24576 KB |
Output is correct |
9 |
Correct |
31 ms |
24696 KB |
Output is correct |
10 |
Correct |
28 ms |
24696 KB |
Output is correct |
11 |
Correct |
29 ms |
24704 KB |
Output is correct |
12 |
Correct |
36 ms |
24676 KB |
Output is correct |
13 |
Correct |
27 ms |
24568 KB |
Output is correct |
14 |
Correct |
28 ms |
24568 KB |
Output is correct |
15 |
Correct |
31 ms |
24696 KB |
Output is correct |
16 |
Correct |
29 ms |
24576 KB |
Output is correct |
17 |
Correct |
30 ms |
24696 KB |
Output is correct |
18 |
Correct |
29 ms |
24704 KB |
Output is correct |
19 |
Correct |
29 ms |
24568 KB |
Output is correct |
20 |
Correct |
28 ms |
24708 KB |
Output is correct |
21 |
Correct |
29 ms |
24576 KB |
Output is correct |
22 |
Correct |
28 ms |
24568 KB |
Output is correct |
23 |
Correct |
29 ms |
24556 KB |
Output is correct |
24 |
Correct |
29 ms |
24704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
24576 KB |
Output is correct |
2 |
Correct |
28 ms |
24568 KB |
Output is correct |
3 |
Correct |
28 ms |
24704 KB |
Output is correct |
4 |
Correct |
32 ms |
24704 KB |
Output is correct |
5 |
Correct |
29 ms |
24676 KB |
Output is correct |
6 |
Correct |
31 ms |
24732 KB |
Output is correct |
7 |
Correct |
34 ms |
24568 KB |
Output is correct |
8 |
Correct |
28 ms |
24576 KB |
Output is correct |
9 |
Correct |
31 ms |
24696 KB |
Output is correct |
10 |
Correct |
28 ms |
24696 KB |
Output is correct |
11 |
Correct |
29 ms |
24704 KB |
Output is correct |
12 |
Correct |
36 ms |
24676 KB |
Output is correct |
13 |
Correct |
27 ms |
24568 KB |
Output is correct |
14 |
Correct |
28 ms |
24568 KB |
Output is correct |
15 |
Correct |
31 ms |
24696 KB |
Output is correct |
16 |
Correct |
29 ms |
24576 KB |
Output is correct |
17 |
Correct |
30 ms |
24696 KB |
Output is correct |
18 |
Correct |
29 ms |
24704 KB |
Output is correct |
19 |
Correct |
29 ms |
24568 KB |
Output is correct |
20 |
Correct |
28 ms |
24708 KB |
Output is correct |
21 |
Correct |
29 ms |
24576 KB |
Output is correct |
22 |
Correct |
28 ms |
24568 KB |
Output is correct |
23 |
Correct |
29 ms |
24556 KB |
Output is correct |
24 |
Correct |
29 ms |
24704 KB |
Output is correct |
25 |
Correct |
227 ms |
29420 KB |
Output is correct |
26 |
Correct |
51 ms |
25208 KB |
Output is correct |
27 |
Correct |
292 ms |
31328 KB |
Output is correct |
28 |
Correct |
294 ms |
31352 KB |
Output is correct |
29 |
Correct |
194 ms |
29432 KB |
Output is correct |
30 |
Correct |
191 ms |
29192 KB |
Output is correct |
31 |
Correct |
221 ms |
30584 KB |
Output is correct |
32 |
Correct |
295 ms |
31352 KB |
Output is correct |
33 |
Correct |
267 ms |
31224 KB |
Output is correct |
34 |
Correct |
152 ms |
27956 KB |
Output is correct |
35 |
Correct |
288 ms |
31484 KB |
Output is correct |
36 |
Correct |
282 ms |
31352 KB |
Output is correct |
37 |
Correct |
145 ms |
28156 KB |
Output is correct |
38 |
Correct |
235 ms |
30500 KB |
Output is correct |
39 |
Correct |
68 ms |
25592 KB |
Output is correct |
40 |
Correct |
280 ms |
30428 KB |
Output is correct |
41 |
Correct |
224 ms |
29108 KB |
Output is correct |
42 |
Correct |
286 ms |
30328 KB |
Output is correct |
43 |
Correct |
100 ms |
26616 KB |
Output is correct |
44 |
Correct |
247 ms |
30584 KB |
Output is correct |
45 |
Correct |
66 ms |
25720 KB |
Output is correct |
46 |
Correct |
259 ms |
30312 KB |
Output is correct |
47 |
Correct |
78 ms |
26232 KB |
Output is correct |
48 |
Correct |
279 ms |
30328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
613 ms |
35960 KB |
Output is correct |
2 |
Correct |
736 ms |
37328 KB |
Output is correct |
3 |
Correct |
429 ms |
33528 KB |
Output is correct |
4 |
Correct |
680 ms |
37240 KB |
Output is correct |
5 |
Correct |
261 ms |
30328 KB |
Output is correct |
6 |
Correct |
623 ms |
37368 KB |
Output is correct |
7 |
Correct |
486 ms |
35448 KB |
Output is correct |
8 |
Correct |
660 ms |
37196 KB |
Output is correct |
9 |
Correct |
93 ms |
26488 KB |
Output is correct |
10 |
Correct |
647 ms |
37240 KB |
Output is correct |
11 |
Correct |
352 ms |
32372 KB |
Output is correct |
12 |
Correct |
694 ms |
37112 KB |
Output is correct |
13 |
Correct |
386 ms |
34920 KB |
Output is correct |
14 |
Correct |
354 ms |
34548 KB |
Output is correct |
15 |
Correct |
377 ms |
33868 KB |
Output is correct |
16 |
Correct |
303 ms |
33904 KB |
Output is correct |
17 |
Correct |
444 ms |
35396 KB |
Output is correct |
18 |
Correct |
289 ms |
34296 KB |
Output is correct |
19 |
Correct |
316 ms |
34260 KB |
Output is correct |
20 |
Correct |
352 ms |
34368 KB |
Output is correct |
21 |
Correct |
330 ms |
34672 KB |
Output is correct |
22 |
Correct |
343 ms |
34520 KB |
Output is correct |
23 |
Correct |
287 ms |
34420 KB |
Output is correct |
24 |
Correct |
303 ms |
33560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
29 ms |
24576 KB |
Output is correct |
2 |
Correct |
28 ms |
24568 KB |
Output is correct |
3 |
Correct |
28 ms |
24704 KB |
Output is correct |
4 |
Correct |
32 ms |
24704 KB |
Output is correct |
5 |
Correct |
29 ms |
24676 KB |
Output is correct |
6 |
Correct |
31 ms |
24732 KB |
Output is correct |
7 |
Correct |
34 ms |
24568 KB |
Output is correct |
8 |
Correct |
28 ms |
24576 KB |
Output is correct |
9 |
Correct |
31 ms |
24696 KB |
Output is correct |
10 |
Correct |
28 ms |
24696 KB |
Output is correct |
11 |
Correct |
29 ms |
24704 KB |
Output is correct |
12 |
Correct |
36 ms |
24676 KB |
Output is correct |
13 |
Correct |
27 ms |
24568 KB |
Output is correct |
14 |
Correct |
28 ms |
24568 KB |
Output is correct |
15 |
Correct |
31 ms |
24696 KB |
Output is correct |
16 |
Correct |
29 ms |
24576 KB |
Output is correct |
17 |
Correct |
30 ms |
24696 KB |
Output is correct |
18 |
Correct |
29 ms |
24704 KB |
Output is correct |
19 |
Correct |
29 ms |
24568 KB |
Output is correct |
20 |
Correct |
28 ms |
24708 KB |
Output is correct |
21 |
Correct |
29 ms |
24576 KB |
Output is correct |
22 |
Correct |
28 ms |
24568 KB |
Output is correct |
23 |
Correct |
29 ms |
24556 KB |
Output is correct |
24 |
Correct |
29 ms |
24704 KB |
Output is correct |
25 |
Correct |
227 ms |
29420 KB |
Output is correct |
26 |
Correct |
51 ms |
25208 KB |
Output is correct |
27 |
Correct |
292 ms |
31328 KB |
Output is correct |
28 |
Correct |
294 ms |
31352 KB |
Output is correct |
29 |
Correct |
194 ms |
29432 KB |
Output is correct |
30 |
Correct |
191 ms |
29192 KB |
Output is correct |
31 |
Correct |
221 ms |
30584 KB |
Output is correct |
32 |
Correct |
295 ms |
31352 KB |
Output is correct |
33 |
Correct |
267 ms |
31224 KB |
Output is correct |
34 |
Correct |
152 ms |
27956 KB |
Output is correct |
35 |
Correct |
288 ms |
31484 KB |
Output is correct |
36 |
Correct |
282 ms |
31352 KB |
Output is correct |
37 |
Correct |
145 ms |
28156 KB |
Output is correct |
38 |
Correct |
235 ms |
30500 KB |
Output is correct |
39 |
Correct |
68 ms |
25592 KB |
Output is correct |
40 |
Correct |
280 ms |
30428 KB |
Output is correct |
41 |
Correct |
224 ms |
29108 KB |
Output is correct |
42 |
Correct |
286 ms |
30328 KB |
Output is correct |
43 |
Correct |
100 ms |
26616 KB |
Output is correct |
44 |
Correct |
247 ms |
30584 KB |
Output is correct |
45 |
Correct |
66 ms |
25720 KB |
Output is correct |
46 |
Correct |
259 ms |
30312 KB |
Output is correct |
47 |
Correct |
78 ms |
26232 KB |
Output is correct |
48 |
Correct |
279 ms |
30328 KB |
Output is correct |
49 |
Correct |
613 ms |
35960 KB |
Output is correct |
50 |
Correct |
736 ms |
37328 KB |
Output is correct |
51 |
Correct |
429 ms |
33528 KB |
Output is correct |
52 |
Correct |
680 ms |
37240 KB |
Output is correct |
53 |
Correct |
261 ms |
30328 KB |
Output is correct |
54 |
Correct |
623 ms |
37368 KB |
Output is correct |
55 |
Correct |
486 ms |
35448 KB |
Output is correct |
56 |
Correct |
660 ms |
37196 KB |
Output is correct |
57 |
Correct |
93 ms |
26488 KB |
Output is correct |
58 |
Correct |
647 ms |
37240 KB |
Output is correct |
59 |
Correct |
352 ms |
32372 KB |
Output is correct |
60 |
Correct |
694 ms |
37112 KB |
Output is correct |
61 |
Correct |
386 ms |
34920 KB |
Output is correct |
62 |
Correct |
354 ms |
34548 KB |
Output is correct |
63 |
Correct |
377 ms |
33868 KB |
Output is correct |
64 |
Correct |
303 ms |
33904 KB |
Output is correct |
65 |
Correct |
444 ms |
35396 KB |
Output is correct |
66 |
Correct |
289 ms |
34296 KB |
Output is correct |
67 |
Correct |
316 ms |
34260 KB |
Output is correct |
68 |
Correct |
352 ms |
34368 KB |
Output is correct |
69 |
Correct |
330 ms |
34672 KB |
Output is correct |
70 |
Correct |
343 ms |
34520 KB |
Output is correct |
71 |
Correct |
287 ms |
34420 KB |
Output is correct |
72 |
Correct |
303 ms |
33560 KB |
Output is correct |
73 |
Correct |
1012 ms |
44804 KB |
Output is correct |
74 |
Correct |
681 ms |
38492 KB |
Output is correct |
75 |
Correct |
973 ms |
43640 KB |
Output is correct |
76 |
Correct |
1344 ms |
48476 KB |
Output is correct |
77 |
Correct |
688 ms |
37524 KB |
Output is correct |
78 |
Correct |
1033 ms |
45560 KB |
Output is correct |
79 |
Correct |
1025 ms |
46352 KB |
Output is correct |
80 |
Correct |
1168 ms |
48460 KB |
Output is correct |
81 |
Correct |
387 ms |
34168 KB |
Output is correct |
82 |
Correct |
872 ms |
43768 KB |
Output is correct |
83 |
Correct |
835 ms |
42416 KB |
Output is correct |
84 |
Correct |
1254 ms |
48364 KB |
Output is correct |
85 |
Correct |
742 ms |
41844 KB |
Output is correct |
86 |
Correct |
993 ms |
44776 KB |
Output is correct |
87 |
Correct |
421 ms |
36084 KB |
Output is correct |
88 |
Correct |
900 ms |
44020 KB |
Output is correct |
89 |
Correct |
831 ms |
43572 KB |
Output is correct |
90 |
Correct |
1006 ms |
44528 KB |
Output is correct |
91 |
Correct |
561 ms |
39028 KB |
Output is correct |
92 |
Correct |
953 ms |
44668 KB |
Output is correct |
93 |
Correct |
501 ms |
37300 KB |
Output is correct |
94 |
Correct |
1104 ms |
44664 KB |
Output is correct |
95 |
Correct |
597 ms |
38384 KB |
Output is correct |
96 |
Correct |
932 ms |
43680 KB |
Output is correct |