#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 mn[N<<1], mx[N<<1], lo[N<<1], hi[N<<1], t[N<<1];
void push(int p, int l, int r) {
t[p] = max({t[p], hi[p] - mn[p], mx[p] - lo[p]});
if(l != r) {
if(mn[p<<1] != INF) {
lo[p<<1] = min(lo[p<<1], lo[p]);
hi[p<<1] = max(hi[p<<1], hi[p]);
}
if(mn[p<<1|1] != INF) {
lo[p<<1|1] = min(lo[p<<1|1], lo[p]);
hi[p<<1|1] = max(hi[p<<1|1], hi[p]);
}
}
lo[p] = INF, hi[p] = -INF;
}
void tag(int x, int k, int p = 1, int l = 1, int r = n) {
push(p, l, r);
if(l == r) {
if(k == -1) mn[p] = INF, mx[p] = -INF;
else mn[p] = mx[p] = k;
return;
}
int mid = l + r >> 1;
if(x <= mid) tag(x, k, p<<1, l, mid);
else tag(x, k, p<<1|1, mid+1, r);
mn[p] = min(mn[p<<1], mn[p<<1|1]), mx[p] = max(mx[p<<1], mx[p<<1|1]);
}
void add(int x, int y, int k, int p = 1, int l = 1, int r = n) {
push(p, l, r);
if(x > r || l > y) return;
if(x <= l && r <= y) {
if(mn[p] == INF) return;
lo[p] = min(lo[p], k), hi[p] = max(hi[p], k);
push(p, l, r);
return;
}
int mid = l + r >> 1;
add(x, y, k, p<<1, l, mid), add(x, y, k, p<<1|1, mid+1, r);
t[p] = max(t[p<<1], t[p<<1|1]);
}
int query(int x, int y, int p = 1, int l = 1, int r = n) {
push(p, l, r);
if(x > r || l > y) return -INF;
if(x <= l && r <= y) return t[p];
int mid = l + r >> 1;
return max(query(x, y, p<<1, l, mid), query(x, y, p<<1|1, mid+1, r));
}
int H[N], A[N], B[N], ans[N];
vector<int> in[N], out[N];
vector<pii> Q[N];
int main() {
fill_n(mn, N<<1, INF), fill_n(mx, N<<1, -INF);
fill_n(lo, N<<1, INF), fill_n(hi, N<<1, -INF);
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);
}
for(int i = 1; i <= n; i++) {
for(int x : in[i]) tag(x, H[x]);
add(i - B[i], i - A[i], H[i]);
for(pii p : Q[i]) ans[p.y] = query(p.x, i);
for(int x : out[i]) tag(x, -1);
}
for(int i = 1; i <= q; i++) {
if(ans[i] > 0) printf("%d\n", ans[i]);
else printf("-1\n");
}
return 0;
}
Compilation message
antennas.cpp: In function 'void tag(int, int, int, int, int)':
antennas.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
antennas.cpp: In function 'void add(int, int, int, int, int, int)':
antennas.cpp:53:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
antennas.cpp: In function 'int query(int, int, int, int, int)':
antennas.cpp:62:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
antennas.cpp: In function 'int main()':
antennas.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
antennas.cpp:75: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:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &q);
~~~~~^~~~~~~~~~
antennas.cpp:81: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 |
25 ms |
27000 KB |
Output is correct |
2 |
Correct |
25 ms |
27128 KB |
Output is correct |
3 |
Correct |
24 ms |
27000 KB |
Output is correct |
4 |
Correct |
25 ms |
27128 KB |
Output is correct |
5 |
Correct |
25 ms |
27128 KB |
Output is correct |
6 |
Correct |
24 ms |
27000 KB |
Output is correct |
7 |
Correct |
26 ms |
27100 KB |
Output is correct |
8 |
Correct |
25 ms |
27004 KB |
Output is correct |
9 |
Correct |
25 ms |
27000 KB |
Output is correct |
10 |
Correct |
26 ms |
27000 KB |
Output is correct |
11 |
Correct |
25 ms |
27000 KB |
Output is correct |
12 |
Correct |
25 ms |
27000 KB |
Output is correct |
13 |
Correct |
25 ms |
27000 KB |
Output is correct |
14 |
Correct |
25 ms |
27100 KB |
Output is correct |
15 |
Correct |
25 ms |
27000 KB |
Output is correct |
16 |
Correct |
25 ms |
27004 KB |
Output is correct |
17 |
Correct |
31 ms |
27124 KB |
Output is correct |
18 |
Correct |
26 ms |
27000 KB |
Output is correct |
19 |
Correct |
26 ms |
27000 KB |
Output is correct |
20 |
Correct |
25 ms |
27128 KB |
Output is correct |
21 |
Correct |
25 ms |
27000 KB |
Output is correct |
22 |
Correct |
25 ms |
27000 KB |
Output is correct |
23 |
Correct |
25 ms |
27156 KB |
Output is correct |
24 |
Correct |
28 ms |
27128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
27000 KB |
Output is correct |
2 |
Correct |
25 ms |
27128 KB |
Output is correct |
3 |
Correct |
24 ms |
27000 KB |
Output is correct |
4 |
Correct |
25 ms |
27128 KB |
Output is correct |
5 |
Correct |
25 ms |
27128 KB |
Output is correct |
6 |
Correct |
24 ms |
27000 KB |
Output is correct |
7 |
Correct |
26 ms |
27100 KB |
Output is correct |
8 |
Correct |
25 ms |
27004 KB |
Output is correct |
9 |
Correct |
25 ms |
27000 KB |
Output is correct |
10 |
Correct |
26 ms |
27000 KB |
Output is correct |
11 |
Correct |
25 ms |
27000 KB |
Output is correct |
12 |
Correct |
25 ms |
27000 KB |
Output is correct |
13 |
Correct |
25 ms |
27000 KB |
Output is correct |
14 |
Correct |
25 ms |
27100 KB |
Output is correct |
15 |
Correct |
25 ms |
27000 KB |
Output is correct |
16 |
Correct |
25 ms |
27004 KB |
Output is correct |
17 |
Correct |
31 ms |
27124 KB |
Output is correct |
18 |
Correct |
26 ms |
27000 KB |
Output is correct |
19 |
Correct |
26 ms |
27000 KB |
Output is correct |
20 |
Correct |
25 ms |
27128 KB |
Output is correct |
21 |
Correct |
25 ms |
27000 KB |
Output is correct |
22 |
Correct |
25 ms |
27000 KB |
Output is correct |
23 |
Correct |
25 ms |
27156 KB |
Output is correct |
24 |
Correct |
28 ms |
27128 KB |
Output is correct |
25 |
Correct |
145 ms |
30592 KB |
Output is correct |
26 |
Correct |
40 ms |
27512 KB |
Output is correct |
27 |
Correct |
192 ms |
31964 KB |
Output is correct |
28 |
Correct |
195 ms |
32144 KB |
Output is correct |
29 |
Correct |
134 ms |
30676 KB |
Output is correct |
30 |
Correct |
138 ms |
30328 KB |
Output is correct |
31 |
Correct |
145 ms |
31484 KB |
Output is correct |
32 |
Correct |
194 ms |
31980 KB |
Output is correct |
33 |
Correct |
176 ms |
31736 KB |
Output is correct |
34 |
Correct |
107 ms |
29372 KB |
Output is correct |
35 |
Correct |
189 ms |
31992 KB |
Output is correct |
36 |
Correct |
196 ms |
31996 KB |
Output is correct |
37 |
Correct |
111 ms |
29308 KB |
Output is correct |
38 |
Correct |
177 ms |
31096 KB |
Output is correct |
39 |
Correct |
47 ms |
27640 KB |
Output is correct |
40 |
Correct |
176 ms |
31084 KB |
Output is correct |
41 |
Correct |
135 ms |
29940 KB |
Output is correct |
42 |
Correct |
177 ms |
30968 KB |
Output is correct |
43 |
Correct |
76 ms |
28536 KB |
Output is correct |
44 |
Correct |
177 ms |
30972 KB |
Output is correct |
45 |
Correct |
52 ms |
27768 KB |
Output is correct |
46 |
Correct |
201 ms |
31096 KB |
Output is correct |
47 |
Correct |
65 ms |
28064 KB |
Output is correct |
48 |
Correct |
177 ms |
31116 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
345 ms |
34292 KB |
Output is correct |
2 |
Correct |
377 ms |
35020 KB |
Output is correct |
3 |
Correct |
260 ms |
33124 KB |
Output is correct |
4 |
Correct |
414 ms |
35012 KB |
Output is correct |
5 |
Correct |
175 ms |
30748 KB |
Output is correct |
6 |
Correct |
380 ms |
34964 KB |
Output is correct |
7 |
Correct |
331 ms |
34160 KB |
Output is correct |
8 |
Correct |
381 ms |
34932 KB |
Output is correct |
9 |
Correct |
66 ms |
28184 KB |
Output is correct |
10 |
Correct |
376 ms |
34972 KB |
Output is correct |
11 |
Correct |
221 ms |
31736 KB |
Output is correct |
12 |
Correct |
391 ms |
34936 KB |
Output is correct |
13 |
Correct |
274 ms |
31740 KB |
Output is correct |
14 |
Correct |
258 ms |
31700 KB |
Output is correct |
15 |
Correct |
248 ms |
31852 KB |
Output is correct |
16 |
Correct |
217 ms |
32312 KB |
Output is correct |
17 |
Correct |
271 ms |
31872 KB |
Output is correct |
18 |
Correct |
247 ms |
32376 KB |
Output is correct |
19 |
Correct |
260 ms |
31524 KB |
Output is correct |
20 |
Correct |
254 ms |
31812 KB |
Output is correct |
21 |
Correct |
266 ms |
31528 KB |
Output is correct |
22 |
Correct |
273 ms |
31948 KB |
Output is correct |
23 |
Correct |
289 ms |
31596 KB |
Output is correct |
24 |
Correct |
219 ms |
31736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
27000 KB |
Output is correct |
2 |
Correct |
25 ms |
27128 KB |
Output is correct |
3 |
Correct |
24 ms |
27000 KB |
Output is correct |
4 |
Correct |
25 ms |
27128 KB |
Output is correct |
5 |
Correct |
25 ms |
27128 KB |
Output is correct |
6 |
Correct |
24 ms |
27000 KB |
Output is correct |
7 |
Correct |
26 ms |
27100 KB |
Output is correct |
8 |
Correct |
25 ms |
27004 KB |
Output is correct |
9 |
Correct |
25 ms |
27000 KB |
Output is correct |
10 |
Correct |
26 ms |
27000 KB |
Output is correct |
11 |
Correct |
25 ms |
27000 KB |
Output is correct |
12 |
Correct |
25 ms |
27000 KB |
Output is correct |
13 |
Correct |
25 ms |
27000 KB |
Output is correct |
14 |
Correct |
25 ms |
27100 KB |
Output is correct |
15 |
Correct |
25 ms |
27000 KB |
Output is correct |
16 |
Correct |
25 ms |
27004 KB |
Output is correct |
17 |
Correct |
31 ms |
27124 KB |
Output is correct |
18 |
Correct |
26 ms |
27000 KB |
Output is correct |
19 |
Correct |
26 ms |
27000 KB |
Output is correct |
20 |
Correct |
25 ms |
27128 KB |
Output is correct |
21 |
Correct |
25 ms |
27000 KB |
Output is correct |
22 |
Correct |
25 ms |
27000 KB |
Output is correct |
23 |
Correct |
25 ms |
27156 KB |
Output is correct |
24 |
Correct |
28 ms |
27128 KB |
Output is correct |
25 |
Correct |
145 ms |
30592 KB |
Output is correct |
26 |
Correct |
40 ms |
27512 KB |
Output is correct |
27 |
Correct |
192 ms |
31964 KB |
Output is correct |
28 |
Correct |
195 ms |
32144 KB |
Output is correct |
29 |
Correct |
134 ms |
30676 KB |
Output is correct |
30 |
Correct |
138 ms |
30328 KB |
Output is correct |
31 |
Correct |
145 ms |
31484 KB |
Output is correct |
32 |
Correct |
194 ms |
31980 KB |
Output is correct |
33 |
Correct |
176 ms |
31736 KB |
Output is correct |
34 |
Correct |
107 ms |
29372 KB |
Output is correct |
35 |
Correct |
189 ms |
31992 KB |
Output is correct |
36 |
Correct |
196 ms |
31996 KB |
Output is correct |
37 |
Correct |
111 ms |
29308 KB |
Output is correct |
38 |
Correct |
177 ms |
31096 KB |
Output is correct |
39 |
Correct |
47 ms |
27640 KB |
Output is correct |
40 |
Correct |
176 ms |
31084 KB |
Output is correct |
41 |
Correct |
135 ms |
29940 KB |
Output is correct |
42 |
Correct |
177 ms |
30968 KB |
Output is correct |
43 |
Correct |
76 ms |
28536 KB |
Output is correct |
44 |
Correct |
177 ms |
30972 KB |
Output is correct |
45 |
Correct |
52 ms |
27768 KB |
Output is correct |
46 |
Correct |
201 ms |
31096 KB |
Output is correct |
47 |
Correct |
65 ms |
28064 KB |
Output is correct |
48 |
Correct |
177 ms |
31116 KB |
Output is correct |
49 |
Correct |
345 ms |
34292 KB |
Output is correct |
50 |
Correct |
377 ms |
35020 KB |
Output is correct |
51 |
Correct |
260 ms |
33124 KB |
Output is correct |
52 |
Correct |
414 ms |
35012 KB |
Output is correct |
53 |
Correct |
175 ms |
30748 KB |
Output is correct |
54 |
Correct |
380 ms |
34964 KB |
Output is correct |
55 |
Correct |
331 ms |
34160 KB |
Output is correct |
56 |
Correct |
381 ms |
34932 KB |
Output is correct |
57 |
Correct |
66 ms |
28184 KB |
Output is correct |
58 |
Correct |
376 ms |
34972 KB |
Output is correct |
59 |
Correct |
221 ms |
31736 KB |
Output is correct |
60 |
Correct |
391 ms |
34936 KB |
Output is correct |
61 |
Correct |
274 ms |
31740 KB |
Output is correct |
62 |
Correct |
258 ms |
31700 KB |
Output is correct |
63 |
Correct |
248 ms |
31852 KB |
Output is correct |
64 |
Correct |
217 ms |
32312 KB |
Output is correct |
65 |
Correct |
271 ms |
31872 KB |
Output is correct |
66 |
Correct |
247 ms |
32376 KB |
Output is correct |
67 |
Correct |
260 ms |
31524 KB |
Output is correct |
68 |
Correct |
254 ms |
31812 KB |
Output is correct |
69 |
Correct |
266 ms |
31528 KB |
Output is correct |
70 |
Correct |
273 ms |
31948 KB |
Output is correct |
71 |
Correct |
289 ms |
31596 KB |
Output is correct |
72 |
Correct |
219 ms |
31736 KB |
Output is correct |
73 |
Correct |
625 ms |
39508 KB |
Output is correct |
74 |
Correct |
415 ms |
35704 KB |
Output is correct |
75 |
Correct |
588 ms |
39340 KB |
Output is correct |
76 |
Correct |
739 ms |
41424 KB |
Output is correct |
77 |
Correct |
407 ms |
35196 KB |
Output is correct |
78 |
Correct |
617 ms |
39580 KB |
Output is correct |
79 |
Correct |
659 ms |
40576 KB |
Output is correct |
80 |
Correct |
753 ms |
41380 KB |
Output is correct |
81 |
Correct |
321 ms |
33468 KB |
Output is correct |
82 |
Correct |
558 ms |
38464 KB |
Output is correct |
83 |
Correct |
538 ms |
37924 KB |
Output is correct |
84 |
Correct |
750 ms |
41592 KB |
Output is correct |
85 |
Correct |
480 ms |
36136 KB |
Output is correct |
86 |
Correct |
596 ms |
38040 KB |
Output is correct |
87 |
Correct |
305 ms |
33784 KB |
Output is correct |
88 |
Correct |
554 ms |
38520 KB |
Output is correct |
89 |
Correct |
544 ms |
36900 KB |
Output is correct |
90 |
Correct |
588 ms |
38520 KB |
Output is correct |
91 |
Correct |
384 ms |
34660 KB |
Output is correct |
92 |
Correct |
610 ms |
38048 KB |
Output is correct |
93 |
Correct |
332 ms |
33632 KB |
Output is correct |
94 |
Correct |
604 ms |
38152 KB |
Output is correct |
95 |
Correct |
365 ms |
34284 KB |
Output is correct |
96 |
Correct |
558 ms |
38176 KB |
Output is correct |