#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 1 << 18;
const int INF = 1e9 + 1;
int n, q;
int t1[N << 1], t2[N << 1], lz[N << 1];
void tag(int p, int x) {
t2[p] = max(t2[p], t1[p] + x);
lz[p] = max(lz[p], x);
}
void push(int p, int l, int r) {
if(l != r) tag(p << 1, lz[p]), tag(p << 1 | 1, lz[p]);
lz[p] = -INF;
}
void update(int x, int k, int p = 1, int l = 1, int r = n) {
push(p, l, r);
if(l == r) return void(t1[p] = k);
int mid = (l + r) >> 1;
if(x <= mid) update(x, k, p<<1, l, mid);
else update(x, k, p<<1|1, mid+1, r);
t1[p] = max(t1[p<<1], t1[p<<1|1]), t2[p] = max(t2[p<<1], t2[p<<1|1]);
}
void add(int x, int y, int k, int p = 1, int l = 1, int r = n) {
if(x <= l && r <= y) return void(tag(p, k));
push(p, l, r);
int mid = (l + r) >> 1;
if(x <= mid) add(x, y, k, p<<1, l, mid);
if(mid < y) add(x, y, k, p<<1|1, mid+1, r);
t1[p] = max(t1[p<<1], t1[p<<1|1]), t2[p] = max(t2[p<<1], t2[p<<1|1]);
}
int query(int x, int y, int p = 1, int l = 1, int r = n) {
if(x <= l && r <= y) return t2[p];
push(p, l, r);
int mid = (l + r) >> 1, ret = -INF;
if(x <= mid) ret = max(ret, query(x, y, p<<1, l, mid));
if(mid < y) ret = max(ret, query(x, y, p<<1|1, mid+1, r));
return ret;
}
int H[N], A[N], B[N], ans[N];
vector<int> in[N], out[N];
vector<pii> Q[N];
void solve() {
fill_n(t1, N << 1, -INF), fill_n(t2, N << 1, -INF), fill_n(lz, N << 1, -INF);
for(int i = 1; i <= n; i++) {
for(int x : in[i]) update(x, -H[x]);
if(i - A[i] > 0) add(max(i - B[i], 1), i - A[i], H[i]);
for(pii p : Q[i]) ans[p.y] = max(ans[p.y], query(p.x, i));
for(int x : out[i]) update(x, -INF);
}
}
int main() {
memset(ans, -1, sizeof ans);
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%d %d %d", H+i, A+i, B+i);
if(i + A[i] <= n) in[i + A[i]].emplace_back(i);
if(i + B[i] <= n) out[i + B[i]].emplace_back(i);
}
scanf("%d", &q);
for(int i = 1, a, b; i <= q; i++) {
scanf("%d %d", &a, &b);
Q[b].emplace_back(a, i);
}
solve();
for(int i = 1; i <= n; i++) H[i] = -H[i];
solve();
for(int i = 1; i <= q; i++) printf("%d\n", ans[i]);
return 0;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
antennas.cpp:71:14: 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:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
antennas.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
25976 KB |
Output is correct |
2 |
Correct |
23 ms |
25980 KB |
Output is correct |
3 |
Correct |
22 ms |
25976 KB |
Output is correct |
4 |
Correct |
22 ms |
25976 KB |
Output is correct |
5 |
Correct |
22 ms |
25976 KB |
Output is correct |
6 |
Correct |
22 ms |
25976 KB |
Output is correct |
7 |
Correct |
22 ms |
25976 KB |
Output is correct |
8 |
Correct |
23 ms |
25976 KB |
Output is correct |
9 |
Correct |
23 ms |
25976 KB |
Output is correct |
10 |
Correct |
22 ms |
25976 KB |
Output is correct |
11 |
Correct |
22 ms |
25976 KB |
Output is correct |
12 |
Correct |
22 ms |
25976 KB |
Output is correct |
13 |
Correct |
23 ms |
25976 KB |
Output is correct |
14 |
Correct |
23 ms |
25976 KB |
Output is correct |
15 |
Correct |
22 ms |
25976 KB |
Output is correct |
16 |
Correct |
23 ms |
25976 KB |
Output is correct |
17 |
Correct |
22 ms |
25980 KB |
Output is correct |
18 |
Correct |
22 ms |
25976 KB |
Output is correct |
19 |
Correct |
23 ms |
25976 KB |
Output is correct |
20 |
Correct |
22 ms |
25976 KB |
Output is correct |
21 |
Correct |
22 ms |
25976 KB |
Output is correct |
22 |
Correct |
23 ms |
25976 KB |
Output is correct |
23 |
Correct |
23 ms |
26232 KB |
Output is correct |
24 |
Correct |
22 ms |
25976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
25976 KB |
Output is correct |
2 |
Correct |
23 ms |
25980 KB |
Output is correct |
3 |
Correct |
22 ms |
25976 KB |
Output is correct |
4 |
Correct |
22 ms |
25976 KB |
Output is correct |
5 |
Correct |
22 ms |
25976 KB |
Output is correct |
6 |
Correct |
22 ms |
25976 KB |
Output is correct |
7 |
Correct |
22 ms |
25976 KB |
Output is correct |
8 |
Correct |
23 ms |
25976 KB |
Output is correct |
9 |
Correct |
23 ms |
25976 KB |
Output is correct |
10 |
Correct |
22 ms |
25976 KB |
Output is correct |
11 |
Correct |
22 ms |
25976 KB |
Output is correct |
12 |
Correct |
22 ms |
25976 KB |
Output is correct |
13 |
Correct |
23 ms |
25976 KB |
Output is correct |
14 |
Correct |
23 ms |
25976 KB |
Output is correct |
15 |
Correct |
22 ms |
25976 KB |
Output is correct |
16 |
Correct |
23 ms |
25976 KB |
Output is correct |
17 |
Correct |
22 ms |
25980 KB |
Output is correct |
18 |
Correct |
22 ms |
25976 KB |
Output is correct |
19 |
Correct |
23 ms |
25976 KB |
Output is correct |
20 |
Correct |
22 ms |
25976 KB |
Output is correct |
21 |
Correct |
22 ms |
25976 KB |
Output is correct |
22 |
Correct |
23 ms |
25976 KB |
Output is correct |
23 |
Correct |
23 ms |
26232 KB |
Output is correct |
24 |
Correct |
22 ms |
25976 KB |
Output is correct |
25 |
Correct |
137 ms |
30200 KB |
Output is correct |
26 |
Correct |
37 ms |
26488 KB |
Output is correct |
27 |
Correct |
184 ms |
31992 KB |
Output is correct |
28 |
Correct |
187 ms |
32120 KB |
Output is correct |
29 |
Correct |
136 ms |
30200 KB |
Output is correct |
30 |
Correct |
136 ms |
30072 KB |
Output is correct |
31 |
Correct |
147 ms |
31096 KB |
Output is correct |
32 |
Correct |
192 ms |
31992 KB |
Output is correct |
33 |
Correct |
183 ms |
31584 KB |
Output is correct |
34 |
Correct |
106 ms |
28920 KB |
Output is correct |
35 |
Correct |
188 ms |
31888 KB |
Output is correct |
36 |
Correct |
193 ms |
32120 KB |
Output is correct |
37 |
Correct |
117 ms |
28920 KB |
Output is correct |
38 |
Correct |
186 ms |
31096 KB |
Output is correct |
39 |
Correct |
47 ms |
26872 KB |
Output is correct |
40 |
Correct |
185 ms |
31096 KB |
Output is correct |
41 |
Correct |
145 ms |
29688 KB |
Output is correct |
42 |
Correct |
185 ms |
31180 KB |
Output is correct |
43 |
Correct |
78 ms |
27772 KB |
Output is correct |
44 |
Correct |
187 ms |
31112 KB |
Output is correct |
45 |
Correct |
52 ms |
27004 KB |
Output is correct |
46 |
Correct |
187 ms |
31096 KB |
Output is correct |
47 |
Correct |
66 ms |
27324 KB |
Output is correct |
48 |
Correct |
188 ms |
31096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
373 ms |
35320 KB |
Output is correct |
2 |
Correct |
399 ms |
36472 KB |
Output is correct |
3 |
Correct |
264 ms |
33292 KB |
Output is correct |
4 |
Correct |
407 ms |
36472 KB |
Output is correct |
5 |
Correct |
188 ms |
30712 KB |
Output is correct |
6 |
Correct |
432 ms |
36476 KB |
Output is correct |
7 |
Correct |
373 ms |
35064 KB |
Output is correct |
8 |
Correct |
439 ms |
36456 KB |
Output is correct |
9 |
Correct |
68 ms |
27516 KB |
Output is correct |
10 |
Correct |
429 ms |
36412 KB |
Output is correct |
11 |
Correct |
247 ms |
32376 KB |
Output is correct |
12 |
Correct |
443 ms |
36344 KB |
Output is correct |
13 |
Correct |
336 ms |
34068 KB |
Output is correct |
14 |
Correct |
333 ms |
34140 KB |
Output is correct |
15 |
Correct |
320 ms |
34176 KB |
Output is correct |
16 |
Correct |
297 ms |
34476 KB |
Output is correct |
17 |
Correct |
320 ms |
34208 KB |
Output is correct |
18 |
Correct |
296 ms |
34552 KB |
Output is correct |
19 |
Correct |
301 ms |
33744 KB |
Output is correct |
20 |
Correct |
290 ms |
34112 KB |
Output is correct |
21 |
Correct |
316 ms |
33756 KB |
Output is correct |
22 |
Correct |
306 ms |
34084 KB |
Output is correct |
23 |
Correct |
313 ms |
33908 KB |
Output is correct |
24 |
Correct |
260 ms |
34168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
25976 KB |
Output is correct |
2 |
Correct |
23 ms |
25980 KB |
Output is correct |
3 |
Correct |
22 ms |
25976 KB |
Output is correct |
4 |
Correct |
22 ms |
25976 KB |
Output is correct |
5 |
Correct |
22 ms |
25976 KB |
Output is correct |
6 |
Correct |
22 ms |
25976 KB |
Output is correct |
7 |
Correct |
22 ms |
25976 KB |
Output is correct |
8 |
Correct |
23 ms |
25976 KB |
Output is correct |
9 |
Correct |
23 ms |
25976 KB |
Output is correct |
10 |
Correct |
22 ms |
25976 KB |
Output is correct |
11 |
Correct |
22 ms |
25976 KB |
Output is correct |
12 |
Correct |
22 ms |
25976 KB |
Output is correct |
13 |
Correct |
23 ms |
25976 KB |
Output is correct |
14 |
Correct |
23 ms |
25976 KB |
Output is correct |
15 |
Correct |
22 ms |
25976 KB |
Output is correct |
16 |
Correct |
23 ms |
25976 KB |
Output is correct |
17 |
Correct |
22 ms |
25980 KB |
Output is correct |
18 |
Correct |
22 ms |
25976 KB |
Output is correct |
19 |
Correct |
23 ms |
25976 KB |
Output is correct |
20 |
Correct |
22 ms |
25976 KB |
Output is correct |
21 |
Correct |
22 ms |
25976 KB |
Output is correct |
22 |
Correct |
23 ms |
25976 KB |
Output is correct |
23 |
Correct |
23 ms |
26232 KB |
Output is correct |
24 |
Correct |
22 ms |
25976 KB |
Output is correct |
25 |
Correct |
137 ms |
30200 KB |
Output is correct |
26 |
Correct |
37 ms |
26488 KB |
Output is correct |
27 |
Correct |
184 ms |
31992 KB |
Output is correct |
28 |
Correct |
187 ms |
32120 KB |
Output is correct |
29 |
Correct |
136 ms |
30200 KB |
Output is correct |
30 |
Correct |
136 ms |
30072 KB |
Output is correct |
31 |
Correct |
147 ms |
31096 KB |
Output is correct |
32 |
Correct |
192 ms |
31992 KB |
Output is correct |
33 |
Correct |
183 ms |
31584 KB |
Output is correct |
34 |
Correct |
106 ms |
28920 KB |
Output is correct |
35 |
Correct |
188 ms |
31888 KB |
Output is correct |
36 |
Correct |
193 ms |
32120 KB |
Output is correct |
37 |
Correct |
117 ms |
28920 KB |
Output is correct |
38 |
Correct |
186 ms |
31096 KB |
Output is correct |
39 |
Correct |
47 ms |
26872 KB |
Output is correct |
40 |
Correct |
185 ms |
31096 KB |
Output is correct |
41 |
Correct |
145 ms |
29688 KB |
Output is correct |
42 |
Correct |
185 ms |
31180 KB |
Output is correct |
43 |
Correct |
78 ms |
27772 KB |
Output is correct |
44 |
Correct |
187 ms |
31112 KB |
Output is correct |
45 |
Correct |
52 ms |
27004 KB |
Output is correct |
46 |
Correct |
187 ms |
31096 KB |
Output is correct |
47 |
Correct |
66 ms |
27324 KB |
Output is correct |
48 |
Correct |
188 ms |
31096 KB |
Output is correct |
49 |
Correct |
373 ms |
35320 KB |
Output is correct |
50 |
Correct |
399 ms |
36472 KB |
Output is correct |
51 |
Correct |
264 ms |
33292 KB |
Output is correct |
52 |
Correct |
407 ms |
36472 KB |
Output is correct |
53 |
Correct |
188 ms |
30712 KB |
Output is correct |
54 |
Correct |
432 ms |
36476 KB |
Output is correct |
55 |
Correct |
373 ms |
35064 KB |
Output is correct |
56 |
Correct |
439 ms |
36456 KB |
Output is correct |
57 |
Correct |
68 ms |
27516 KB |
Output is correct |
58 |
Correct |
429 ms |
36412 KB |
Output is correct |
59 |
Correct |
247 ms |
32376 KB |
Output is correct |
60 |
Correct |
443 ms |
36344 KB |
Output is correct |
61 |
Correct |
336 ms |
34068 KB |
Output is correct |
62 |
Correct |
333 ms |
34140 KB |
Output is correct |
63 |
Correct |
320 ms |
34176 KB |
Output is correct |
64 |
Correct |
297 ms |
34476 KB |
Output is correct |
65 |
Correct |
320 ms |
34208 KB |
Output is correct |
66 |
Correct |
296 ms |
34552 KB |
Output is correct |
67 |
Correct |
301 ms |
33744 KB |
Output is correct |
68 |
Correct |
290 ms |
34112 KB |
Output is correct |
69 |
Correct |
316 ms |
33756 KB |
Output is correct |
70 |
Correct |
306 ms |
34084 KB |
Output is correct |
71 |
Correct |
313 ms |
33908 KB |
Output is correct |
72 |
Correct |
260 ms |
34168 KB |
Output is correct |
73 |
Correct |
616 ms |
41724 KB |
Output is correct |
74 |
Correct |
422 ms |
37240 KB |
Output is correct |
75 |
Correct |
612 ms |
41208 KB |
Output is correct |
76 |
Correct |
749 ms |
44760 KB |
Output is correct |
77 |
Correct |
392 ms |
36344 KB |
Output is correct |
78 |
Correct |
618 ms |
42232 KB |
Output is correct |
79 |
Correct |
680 ms |
43128 KB |
Output is correct |
80 |
Correct |
746 ms |
44792 KB |
Output is correct |
81 |
Correct |
288 ms |
34296 KB |
Output is correct |
82 |
Correct |
581 ms |
40824 KB |
Output is correct |
83 |
Correct |
543 ms |
40316 KB |
Output is correct |
84 |
Correct |
761 ms |
44792 KB |
Output is correct |
85 |
Correct |
556 ms |
38344 KB |
Output is correct |
86 |
Correct |
638 ms |
41284 KB |
Output is correct |
87 |
Correct |
339 ms |
35320 KB |
Output is correct |
88 |
Correct |
586 ms |
41724 KB |
Output is correct |
89 |
Correct |
567 ms |
39588 KB |
Output is correct |
90 |
Correct |
653 ms |
41720 KB |
Output is correct |
91 |
Correct |
402 ms |
36564 KB |
Output is correct |
92 |
Correct |
649 ms |
41036 KB |
Output is correct |
93 |
Correct |
378 ms |
35356 KB |
Output is correct |
94 |
Correct |
674 ms |
41328 KB |
Output is correct |
95 |
Correct |
388 ms |
36212 KB |
Output is correct |
96 |
Correct |
588 ms |
41196 KB |
Output is correct |