#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200000
#define Q 200000
#define N_ (1 << 18) /* N_ = pow2(ceil(log2(N))) */
#define INF 0x3f3f3f3f
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
int *eh[N], eo[N], *ei[N], eo_[N];
void append(int **ej, int *eo, int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
int st[N_ * 2], mn[N_ * 2], lz[N_ * 2], h_, n_;
void init() {
int i;
for (i = 1; i < n_ * 2; i++)
st[i] = -INF, mn[i] = INF, lz[i] = -INF;
}
void put(int i, int x) {
lz[i] = max(lz[i], x);
st[i] = max(st[i], lz[i] == -INF || mn[i] == INF ? -INF : lz[i] - mn[i]);
}
void pus(int i) {
if (lz[i] != -INF)
put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = -INF;
}
void pul(int i) {
if (lz[i] == -INF) {
int l = i << 1, r = l | 1;
st[i] = max(st[l], st[r]);
mn[i] = min(mn[l], mn[r]);
}
}
void push(int i) {
int h;
for (h = h_; h > 0; h--)
pus(i >> h);
}
void pull(int i) {
while (i > 1)
pul(i >>= 1);
}
void update1(int i, int x) {
i += n_;
push(i);
st[i] = -INF, mn[i] = x, lz[i] = -INF;
pull(i);
}
void update2(int l, int r, int x) {
int l_ = l += n_, r_ = r += n_;
push(l_), push(r_);
for ( ; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
put(l++, x);
if ((r & 1) == 0)
put(r--, x);
}
pull(l_), pull(r_);
}
void update3(int i) {
i += n_;
push(i);
st[i] = lz[i] == -INF || mn[i] == INF ? -INF : lz[i] - mn[i], mn[i] = INF;
pull(i);
}
int query(int l, int r) {
int x;
push(l += n_), push(r += n_);
x = -INF;
for ( ; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
x = max(x, st[l++]);
if ((r & 1) == 0)
x = max(x, st[r--]);
}
return x;
}
int main() {
static int yy[N], aa[N], bb[N], ll[Q], rr[Q], ans[Q];
int n, q, h, i, r, t, o, o_;
scanf("%d", &n);
for (i = 0; i < n; i++)
eh[i] = (int *) malloc(2 * sizeof *eh[i]);
for (i = 0; i < n; i++)
scanf("%d%d%d", &yy[i], &aa[i], &bb[i]);
scanf("%d", &q);
for (h = 0; h < q; h++) {
scanf("%d%d", &ll[h], &rr[h]), ll[h]--, rr[h]--;
append(eh, eo, rr[h], h);
}
for (i = 0; i < n; i++)
ei[i] = (int *) malloc(2 * sizeof *ei[i]);
for (i = 0; i < n; i++) {
if (i + aa[i] < n)
append(ei, eo_, i + aa[i], i << 1 | 0);
if (i + bb[i] + 1 < n)
append(ei, eo_, i + bb[i] + 1, i << 1 | 1);
}
h_ = 0;
while (1 << h_ < n)
h_++;
n_ = 1 << h_;
memset(ans, -1, q * sizeof *ans);
for (t = 0; t < 2; t++) {
init();
for (r = 0; r < n; r++) {
for (o_ = eo_[r]; o_--; ) {
i = ei[r][o_];
if ((i & 1) == 0)
update1(i >> 1, yy[i >> 1]);
else
update3(i >> 1);
}
for (o = eo[r]; o--; ) {
h = eh[r][o];
ans[h] = max(ans[h], query(ll[h], r));
}
if (r - aa[r] >= 0)
update2(max(r - bb[r], 0), r - aa[r], yy[r]);
for (o = eo[r]; o--; ) {
h = eh[r][o];
ans[h] = max(ans[h], query(ll[h], r));
}
}
for (i = 0; i < n; i++)
yy[i] = -yy[i];
}
for (h = 0; h < q; h++)
printf("%d\n", ans[h]);
return 0;
}
Compilation message
antennas.c: In function 'append':
antennas.c:18:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
18 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
antennas.c: In function 'main':
antennas.c:108:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
antennas.c:112:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | scanf("%d%d%d", &yy[i], &aa[i], &bb[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.c:113:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | scanf("%d", &q);
| ^~~~~~~~~~~~~~~
antennas.c:115:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
115 | scanf("%d%d", &ll[h], &rr[h]), ll[h]--, rr[h]--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
428 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
296 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
292 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
304 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
428 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
296 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
292 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
304 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
85 ms |
5388 KB |
Output is correct |
26 |
Correct |
14 ms |
1108 KB |
Output is correct |
27 |
Correct |
137 ms |
7548 KB |
Output is correct |
28 |
Correct |
131 ms |
7588 KB |
Output is correct |
29 |
Correct |
86 ms |
5388 KB |
Output is correct |
30 |
Correct |
95 ms |
5288 KB |
Output is correct |
31 |
Correct |
97 ms |
6736 KB |
Output is correct |
32 |
Correct |
128 ms |
7584 KB |
Output is correct |
33 |
Correct |
121 ms |
7160 KB |
Output is correct |
34 |
Correct |
70 ms |
3920 KB |
Output is correct |
35 |
Correct |
122 ms |
7456 KB |
Output is correct |
36 |
Correct |
126 ms |
7628 KB |
Output is correct |
37 |
Correct |
70 ms |
4008 KB |
Output is correct |
38 |
Correct |
143 ms |
6692 KB |
Output is correct |
39 |
Correct |
19 ms |
1356 KB |
Output is correct |
40 |
Correct |
119 ms |
6680 KB |
Output is correct |
41 |
Correct |
91 ms |
4988 KB |
Output is correct |
42 |
Correct |
161 ms |
6616 KB |
Output is correct |
43 |
Correct |
44 ms |
2572 KB |
Output is correct |
44 |
Correct |
117 ms |
6676 KB |
Output is correct |
45 |
Correct |
23 ms |
1748 KB |
Output is correct |
46 |
Correct |
149 ms |
6692 KB |
Output is correct |
47 |
Correct |
40 ms |
2056 KB |
Output is correct |
48 |
Correct |
119 ms |
6636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
309 ms |
27492 KB |
Output is correct |
2 |
Correct |
324 ms |
29772 KB |
Output is correct |
3 |
Correct |
246 ms |
22832 KB |
Output is correct |
4 |
Correct |
343 ms |
29824 KB |
Output is correct |
5 |
Correct |
139 ms |
14088 KB |
Output is correct |
6 |
Correct |
340 ms |
29820 KB |
Output is correct |
7 |
Correct |
273 ms |
26716 KB |
Output is correct |
8 |
Correct |
343 ms |
29816 KB |
Output is correct |
9 |
Correct |
44 ms |
4776 KB |
Output is correct |
10 |
Correct |
316 ms |
29824 KB |
Output is correct |
11 |
Correct |
174 ms |
17980 KB |
Output is correct |
12 |
Correct |
360 ms |
29824 KB |
Output is correct |
13 |
Correct |
269 ms |
29956 KB |
Output is correct |
14 |
Correct |
255 ms |
30016 KB |
Output is correct |
15 |
Correct |
212 ms |
30116 KB |
Output is correct |
16 |
Correct |
259 ms |
30272 KB |
Output is correct |
17 |
Correct |
299 ms |
30108 KB |
Output is correct |
18 |
Correct |
246 ms |
30168 KB |
Output is correct |
19 |
Correct |
257 ms |
29944 KB |
Output is correct |
20 |
Correct |
231 ms |
29808 KB |
Output is correct |
21 |
Correct |
236 ms |
29660 KB |
Output is correct |
22 |
Correct |
290 ms |
30008 KB |
Output is correct |
23 |
Correct |
242 ms |
30140 KB |
Output is correct |
24 |
Correct |
270 ms |
30124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
428 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
296 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
292 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
304 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
85 ms |
5388 KB |
Output is correct |
26 |
Correct |
14 ms |
1108 KB |
Output is correct |
27 |
Correct |
137 ms |
7548 KB |
Output is correct |
28 |
Correct |
131 ms |
7588 KB |
Output is correct |
29 |
Correct |
86 ms |
5388 KB |
Output is correct |
30 |
Correct |
95 ms |
5288 KB |
Output is correct |
31 |
Correct |
97 ms |
6736 KB |
Output is correct |
32 |
Correct |
128 ms |
7584 KB |
Output is correct |
33 |
Correct |
121 ms |
7160 KB |
Output is correct |
34 |
Correct |
70 ms |
3920 KB |
Output is correct |
35 |
Correct |
122 ms |
7456 KB |
Output is correct |
36 |
Correct |
126 ms |
7628 KB |
Output is correct |
37 |
Correct |
70 ms |
4008 KB |
Output is correct |
38 |
Correct |
143 ms |
6692 KB |
Output is correct |
39 |
Correct |
19 ms |
1356 KB |
Output is correct |
40 |
Correct |
119 ms |
6680 KB |
Output is correct |
41 |
Correct |
91 ms |
4988 KB |
Output is correct |
42 |
Correct |
161 ms |
6616 KB |
Output is correct |
43 |
Correct |
44 ms |
2572 KB |
Output is correct |
44 |
Correct |
117 ms |
6676 KB |
Output is correct |
45 |
Correct |
23 ms |
1748 KB |
Output is correct |
46 |
Correct |
149 ms |
6692 KB |
Output is correct |
47 |
Correct |
40 ms |
2056 KB |
Output is correct |
48 |
Correct |
119 ms |
6636 KB |
Output is correct |
49 |
Correct |
309 ms |
27492 KB |
Output is correct |
50 |
Correct |
324 ms |
29772 KB |
Output is correct |
51 |
Correct |
246 ms |
22832 KB |
Output is correct |
52 |
Correct |
343 ms |
29824 KB |
Output is correct |
53 |
Correct |
139 ms |
14088 KB |
Output is correct |
54 |
Correct |
340 ms |
29820 KB |
Output is correct |
55 |
Correct |
273 ms |
26716 KB |
Output is correct |
56 |
Correct |
343 ms |
29816 KB |
Output is correct |
57 |
Correct |
44 ms |
4776 KB |
Output is correct |
58 |
Correct |
316 ms |
29824 KB |
Output is correct |
59 |
Correct |
174 ms |
17980 KB |
Output is correct |
60 |
Correct |
360 ms |
29824 KB |
Output is correct |
61 |
Correct |
269 ms |
29956 KB |
Output is correct |
62 |
Correct |
255 ms |
30016 KB |
Output is correct |
63 |
Correct |
212 ms |
30116 KB |
Output is correct |
64 |
Correct |
259 ms |
30272 KB |
Output is correct |
65 |
Correct |
299 ms |
30108 KB |
Output is correct |
66 |
Correct |
246 ms |
30168 KB |
Output is correct |
67 |
Correct |
257 ms |
29944 KB |
Output is correct |
68 |
Correct |
231 ms |
29808 KB |
Output is correct |
69 |
Correct |
236 ms |
29660 KB |
Output is correct |
70 |
Correct |
290 ms |
30008 KB |
Output is correct |
71 |
Correct |
242 ms |
30140 KB |
Output is correct |
72 |
Correct |
270 ms |
30124 KB |
Output is correct |
73 |
Correct |
486 ms |
33268 KB |
Output is correct |
74 |
Correct |
419 ms |
31076 KB |
Output is correct |
75 |
Correct |
478 ms |
30292 KB |
Output is correct |
76 |
Correct |
653 ms |
37564 KB |
Output is correct |
77 |
Correct |
308 ms |
19500 KB |
Output is correct |
78 |
Correct |
509 ms |
35184 KB |
Output is correct |
79 |
Correct |
556 ms |
34380 KB |
Output is correct |
80 |
Correct |
619 ms |
37564 KB |
Output is correct |
81 |
Correct |
246 ms |
11856 KB |
Output is correct |
82 |
Correct |
469 ms |
33908 KB |
Output is correct |
83 |
Correct |
436 ms |
25568 KB |
Output is correct |
84 |
Correct |
644 ms |
37568 KB |
Output is correct |
85 |
Correct |
402 ms |
33976 KB |
Output is correct |
86 |
Correct |
494 ms |
36556 KB |
Output is correct |
87 |
Correct |
265 ms |
31640 KB |
Output is correct |
88 |
Correct |
522 ms |
36912 KB |
Output is correct |
89 |
Correct |
447 ms |
35040 KB |
Output is correct |
90 |
Correct |
510 ms |
36744 KB |
Output is correct |
91 |
Correct |
319 ms |
32528 KB |
Output is correct |
92 |
Correct |
518 ms |
36484 KB |
Output is correct |
93 |
Correct |
308 ms |
31376 KB |
Output is correct |
94 |
Correct |
457 ms |
36512 KB |
Output is correct |
95 |
Correct |
298 ms |
32192 KB |
Output is correct |
96 |
Correct |
508 ms |
36676 KB |
Output is correct |