/* There's someone in my head but it's not me */
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 2e5 + 10;
int n, q, A[N], B[N], h[N]; ll ans[N];
struct node {
ll ret, mn, mx, lzmn, lzmx; node *lc, *rc;
node() : ret(-1), mn(1e18), mx(-1e18), lzmn(1e18), lzmx(-1e18), lc(nullptr), rc(nullptr) {};
void build(int l = 1, int r = n + 1) {
if (r - l < 2) return;
int md = (l + r) >> 1;
lc = new node(), rc = new node();
lc->build(l, md), rc->build(md, r);
}
void shift() {
ret = max({ret, mx - lzmn, lzmx - mn});
if (lc)
lc->lzmn = min(lc->lzmn, lzmn), lc->lzmx = max(lc->lzmx, lzmx);
if (rc)
rc->lzmn = min(rc->lzmn, lzmn), rc->lzmx = max(rc->lzmx, lzmx);
lzmx = -1e18, lzmn = 1e18;
}
void modify(int p, int t, int l = 1, int r = n + 1) {
shift();
if (r - l < 2) {
if (!t) mx = -1e18, mn = 1e18;
else mx = mn = h[p];
return;
}
int md = (l + r) >> 1;
if (p < md) lc->modify(p, t, l, md), rc->shift();
else rc->modify(p, t, md, r), lc->shift();
mx = max(lc->mx, rc->mx), mn = min(lc->mn, rc->mn);
ret = max(lc->ret, rc->ret);
}
void upd(int ql, int qr, ll x, int l = 1, int r = n + 1) {
shift();
if (qr <= l || r <= ql || ql >= qr) return;
if (ql <= l && r <= qr) {
lzmn = min(lzmn, x); lzmx = max(lzmx, x);
return shift();
}
int md = (l + r) >> 1;
lc->upd(ql, qr, x, l, md), rc->upd(ql, qr, x, md, r);
mx = max(lc->mx, rc->mx), mn = min(lc->mn, rc->mn);
ret = max(lc->ret, rc->ret);
}
ll get(int ql, int qr, int l = 1, int r = n + 1) {
shift();
if (qr <= l || r <= ql || ql >= qr) return -1;
if (ql <= l && r <= qr) return ret;
int md = (l + r) >> 1;
return max(lc->get(ql, qr, l, md), rc->get(ql, qr, md, r));
}
};
node* seg; vector<pii> vec[N], Q[N];
int main() {
fill(ans, ans + N, -1);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &h[i], &A[i], &B[i]);
vec[min(n + 1, i + A[i])].push_back({i, 1});
vec[min(n + 1, i + B[i] + 1)].push_back({i, 0});
}
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
int l, r; scanf("%d%d", &l, &r);
Q[r].push_back({l, i});
}
seg = new node();
seg->build();
for (int i = 1; i <= n; i++) {
for (pii &j : vec[i]) {
seg->modify(j.F, j.S);
}
seg->upd(i - B[i], i - A[i] + 1, h[i]);
for (pii &j : Q[i])
ans[j.S] = seg->get(j.F, i + 1);
}
for (int i = 1; i <= q; i++)
printf("%lld\n", ans[i]);
return 0;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
75 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
antennas.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
77 | scanf("%d%d%d", &h[i], &A[i], &B[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
81 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
antennas.cpp:83:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
83 | int l, r; scanf("%d%d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
11212 KB |
Output is correct |
2 |
Correct |
10 ms |
11272 KB |
Output is correct |
3 |
Correct |
9 ms |
11256 KB |
Output is correct |
4 |
Correct |
8 ms |
11280 KB |
Output is correct |
5 |
Correct |
8 ms |
11224 KB |
Output is correct |
6 |
Correct |
8 ms |
11340 KB |
Output is correct |
7 |
Correct |
8 ms |
11212 KB |
Output is correct |
8 |
Correct |
8 ms |
11340 KB |
Output is correct |
9 |
Correct |
8 ms |
11212 KB |
Output is correct |
10 |
Correct |
8 ms |
11340 KB |
Output is correct |
11 |
Correct |
8 ms |
11264 KB |
Output is correct |
12 |
Correct |
8 ms |
11340 KB |
Output is correct |
13 |
Correct |
8 ms |
11212 KB |
Output is correct |
14 |
Correct |
9 ms |
11212 KB |
Output is correct |
15 |
Correct |
8 ms |
11304 KB |
Output is correct |
16 |
Correct |
8 ms |
11276 KB |
Output is correct |
17 |
Correct |
8 ms |
11212 KB |
Output is correct |
18 |
Correct |
8 ms |
11212 KB |
Output is correct |
19 |
Correct |
8 ms |
11212 KB |
Output is correct |
20 |
Correct |
8 ms |
11212 KB |
Output is correct |
21 |
Correct |
8 ms |
11212 KB |
Output is correct |
22 |
Correct |
8 ms |
11340 KB |
Output is correct |
23 |
Correct |
8 ms |
11212 KB |
Output is correct |
24 |
Correct |
8 ms |
11272 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
11212 KB |
Output is correct |
2 |
Correct |
10 ms |
11272 KB |
Output is correct |
3 |
Correct |
9 ms |
11256 KB |
Output is correct |
4 |
Correct |
8 ms |
11280 KB |
Output is correct |
5 |
Correct |
8 ms |
11224 KB |
Output is correct |
6 |
Correct |
8 ms |
11340 KB |
Output is correct |
7 |
Correct |
8 ms |
11212 KB |
Output is correct |
8 |
Correct |
8 ms |
11340 KB |
Output is correct |
9 |
Correct |
8 ms |
11212 KB |
Output is correct |
10 |
Correct |
8 ms |
11340 KB |
Output is correct |
11 |
Correct |
8 ms |
11264 KB |
Output is correct |
12 |
Correct |
8 ms |
11340 KB |
Output is correct |
13 |
Correct |
8 ms |
11212 KB |
Output is correct |
14 |
Correct |
9 ms |
11212 KB |
Output is correct |
15 |
Correct |
8 ms |
11304 KB |
Output is correct |
16 |
Correct |
8 ms |
11276 KB |
Output is correct |
17 |
Correct |
8 ms |
11212 KB |
Output is correct |
18 |
Correct |
8 ms |
11212 KB |
Output is correct |
19 |
Correct |
8 ms |
11212 KB |
Output is correct |
20 |
Correct |
8 ms |
11212 KB |
Output is correct |
21 |
Correct |
8 ms |
11212 KB |
Output is correct |
22 |
Correct |
8 ms |
11340 KB |
Output is correct |
23 |
Correct |
8 ms |
11212 KB |
Output is correct |
24 |
Correct |
8 ms |
11272 KB |
Output is correct |
25 |
Correct |
112 ms |
15484 KB |
Output is correct |
26 |
Correct |
22 ms |
11980 KB |
Output is correct |
27 |
Correct |
180 ms |
17348 KB |
Output is correct |
28 |
Correct |
168 ms |
17472 KB |
Output is correct |
29 |
Correct |
113 ms |
15556 KB |
Output is correct |
30 |
Correct |
114 ms |
15384 KB |
Output is correct |
31 |
Correct |
135 ms |
16356 KB |
Output is correct |
32 |
Correct |
165 ms |
17476 KB |
Output is correct |
33 |
Correct |
154 ms |
16904 KB |
Output is correct |
34 |
Correct |
85 ms |
14404 KB |
Output is correct |
35 |
Correct |
158 ms |
17240 KB |
Output is correct |
36 |
Correct |
166 ms |
17540 KB |
Output is correct |
37 |
Correct |
96 ms |
14404 KB |
Output is correct |
38 |
Correct |
160 ms |
16412 KB |
Output is correct |
39 |
Correct |
30 ms |
12204 KB |
Output is correct |
40 |
Correct |
199 ms |
16508 KB |
Output is correct |
41 |
Correct |
119 ms |
15148 KB |
Output is correct |
42 |
Correct |
182 ms |
16448 KB |
Output is correct |
43 |
Correct |
65 ms |
13224 KB |
Output is correct |
44 |
Correct |
163 ms |
16452 KB |
Output is correct |
45 |
Correct |
34 ms |
12372 KB |
Output is correct |
46 |
Correct |
160 ms |
16412 KB |
Output is correct |
47 |
Correct |
50 ms |
12868 KB |
Output is correct |
48 |
Correct |
165 ms |
16488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
369 ms |
40496 KB |
Output is correct |
2 |
Correct |
398 ms |
43828 KB |
Output is correct |
3 |
Correct |
295 ms |
34096 KB |
Output is correct |
4 |
Correct |
410 ms |
43764 KB |
Output is correct |
5 |
Correct |
158 ms |
26284 KB |
Output is correct |
6 |
Correct |
419 ms |
43756 KB |
Output is correct |
7 |
Correct |
350 ms |
39344 KB |
Output is correct |
8 |
Correct |
406 ms |
43756 KB |
Output is correct |
9 |
Correct |
47 ms |
16324 KB |
Output is correct |
10 |
Correct |
417 ms |
43764 KB |
Output is correct |
11 |
Correct |
253 ms |
31636 KB |
Output is correct |
12 |
Correct |
418 ms |
43760 KB |
Output is correct |
13 |
Correct |
285 ms |
42152 KB |
Output is correct |
14 |
Correct |
261 ms |
42240 KB |
Output is correct |
15 |
Correct |
244 ms |
42124 KB |
Output is correct |
16 |
Correct |
219 ms |
42692 KB |
Output is correct |
17 |
Correct |
267 ms |
42196 KB |
Output is correct |
18 |
Correct |
247 ms |
42552 KB |
Output is correct |
19 |
Correct |
272 ms |
42244 KB |
Output is correct |
20 |
Correct |
248 ms |
42132 KB |
Output is correct |
21 |
Correct |
256 ms |
42136 KB |
Output is correct |
22 |
Correct |
252 ms |
42224 KB |
Output is correct |
23 |
Correct |
256 ms |
42164 KB |
Output is correct |
24 |
Correct |
228 ms |
42160 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
11212 KB |
Output is correct |
2 |
Correct |
10 ms |
11272 KB |
Output is correct |
3 |
Correct |
9 ms |
11256 KB |
Output is correct |
4 |
Correct |
8 ms |
11280 KB |
Output is correct |
5 |
Correct |
8 ms |
11224 KB |
Output is correct |
6 |
Correct |
8 ms |
11340 KB |
Output is correct |
7 |
Correct |
8 ms |
11212 KB |
Output is correct |
8 |
Correct |
8 ms |
11340 KB |
Output is correct |
9 |
Correct |
8 ms |
11212 KB |
Output is correct |
10 |
Correct |
8 ms |
11340 KB |
Output is correct |
11 |
Correct |
8 ms |
11264 KB |
Output is correct |
12 |
Correct |
8 ms |
11340 KB |
Output is correct |
13 |
Correct |
8 ms |
11212 KB |
Output is correct |
14 |
Correct |
9 ms |
11212 KB |
Output is correct |
15 |
Correct |
8 ms |
11304 KB |
Output is correct |
16 |
Correct |
8 ms |
11276 KB |
Output is correct |
17 |
Correct |
8 ms |
11212 KB |
Output is correct |
18 |
Correct |
8 ms |
11212 KB |
Output is correct |
19 |
Correct |
8 ms |
11212 KB |
Output is correct |
20 |
Correct |
8 ms |
11212 KB |
Output is correct |
21 |
Correct |
8 ms |
11212 KB |
Output is correct |
22 |
Correct |
8 ms |
11340 KB |
Output is correct |
23 |
Correct |
8 ms |
11212 KB |
Output is correct |
24 |
Correct |
8 ms |
11272 KB |
Output is correct |
25 |
Correct |
112 ms |
15484 KB |
Output is correct |
26 |
Correct |
22 ms |
11980 KB |
Output is correct |
27 |
Correct |
180 ms |
17348 KB |
Output is correct |
28 |
Correct |
168 ms |
17472 KB |
Output is correct |
29 |
Correct |
113 ms |
15556 KB |
Output is correct |
30 |
Correct |
114 ms |
15384 KB |
Output is correct |
31 |
Correct |
135 ms |
16356 KB |
Output is correct |
32 |
Correct |
165 ms |
17476 KB |
Output is correct |
33 |
Correct |
154 ms |
16904 KB |
Output is correct |
34 |
Correct |
85 ms |
14404 KB |
Output is correct |
35 |
Correct |
158 ms |
17240 KB |
Output is correct |
36 |
Correct |
166 ms |
17540 KB |
Output is correct |
37 |
Correct |
96 ms |
14404 KB |
Output is correct |
38 |
Correct |
160 ms |
16412 KB |
Output is correct |
39 |
Correct |
30 ms |
12204 KB |
Output is correct |
40 |
Correct |
199 ms |
16508 KB |
Output is correct |
41 |
Correct |
119 ms |
15148 KB |
Output is correct |
42 |
Correct |
182 ms |
16448 KB |
Output is correct |
43 |
Correct |
65 ms |
13224 KB |
Output is correct |
44 |
Correct |
163 ms |
16452 KB |
Output is correct |
45 |
Correct |
34 ms |
12372 KB |
Output is correct |
46 |
Correct |
160 ms |
16412 KB |
Output is correct |
47 |
Correct |
50 ms |
12868 KB |
Output is correct |
48 |
Correct |
165 ms |
16488 KB |
Output is correct |
49 |
Correct |
369 ms |
40496 KB |
Output is correct |
50 |
Correct |
398 ms |
43828 KB |
Output is correct |
51 |
Correct |
295 ms |
34096 KB |
Output is correct |
52 |
Correct |
410 ms |
43764 KB |
Output is correct |
53 |
Correct |
158 ms |
26284 KB |
Output is correct |
54 |
Correct |
419 ms |
43756 KB |
Output is correct |
55 |
Correct |
350 ms |
39344 KB |
Output is correct |
56 |
Correct |
406 ms |
43756 KB |
Output is correct |
57 |
Correct |
47 ms |
16324 KB |
Output is correct |
58 |
Correct |
417 ms |
43764 KB |
Output is correct |
59 |
Correct |
253 ms |
31636 KB |
Output is correct |
60 |
Correct |
418 ms |
43760 KB |
Output is correct |
61 |
Correct |
285 ms |
42152 KB |
Output is correct |
62 |
Correct |
261 ms |
42240 KB |
Output is correct |
63 |
Correct |
244 ms |
42124 KB |
Output is correct |
64 |
Correct |
219 ms |
42692 KB |
Output is correct |
65 |
Correct |
267 ms |
42196 KB |
Output is correct |
66 |
Correct |
247 ms |
42552 KB |
Output is correct |
67 |
Correct |
272 ms |
42244 KB |
Output is correct |
68 |
Correct |
248 ms |
42132 KB |
Output is correct |
69 |
Correct |
256 ms |
42136 KB |
Output is correct |
70 |
Correct |
252 ms |
42224 KB |
Output is correct |
71 |
Correct |
256 ms |
42164 KB |
Output is correct |
72 |
Correct |
228 ms |
42160 KB |
Output is correct |
73 |
Correct |
643 ms |
50820 KB |
Output is correct |
74 |
Correct |
434 ms |
48944 KB |
Output is correct |
75 |
Correct |
618 ms |
45164 KB |
Output is correct |
76 |
Correct |
770 ms |
56552 KB |
Output is correct |
77 |
Correct |
385 ms |
33828 KB |
Output is correct |
78 |
Correct |
662 ms |
54052 KB |
Output is correct |
79 |
Correct |
703 ms |
51440 KB |
Output is correct |
80 |
Correct |
765 ms |
56536 KB |
Output is correct |
81 |
Correct |
324 ms |
23760 KB |
Output is correct |
82 |
Correct |
596 ms |
52572 KB |
Output is correct |
83 |
Correct |
540 ms |
42108 KB |
Output is correct |
84 |
Correct |
765 ms |
56544 KB |
Output is correct |
85 |
Correct |
583 ms |
50852 KB |
Output is correct |
86 |
Correct |
643 ms |
53736 KB |
Output is correct |
87 |
Correct |
300 ms |
47752 KB |
Output is correct |
88 |
Correct |
603 ms |
54132 KB |
Output is correct |
89 |
Correct |
553 ms |
52020 KB |
Output is correct |
90 |
Correct |
639 ms |
54140 KB |
Output is correct |
91 |
Correct |
387 ms |
49084 KB |
Output is correct |
92 |
Correct |
646 ms |
53728 KB |
Output is correct |
93 |
Correct |
319 ms |
47908 KB |
Output is correct |
94 |
Correct |
722 ms |
53764 KB |
Output is correct |
95 |
Correct |
363 ms |
48668 KB |
Output is correct |
96 |
Correct |
654 ms |
53708 KB |
Output is correct |