#include <bits/stdc++.h>
using namespace std;
const int DIM = 200005;
const int INF = 1000000007;
int sgt1[DIM << 2], sgt2[DIM << 2], lzy[DIM << 2], ans[DIM];
vector<int> upd[DIM], lst[DIM];
struct Antenna {
int h, a, b; } arr[DIM];
struct Query {
int l, r; } qry[DIM];
void updateLazy(int nd, int le, int ri) {
if (lzy[nd]) {
sgt2[nd] = max(sgt2[nd], lzy[nd] - sgt1[nd]);
if (le != ri) {
lzy[nd << 1] = max(lzy[nd << 1], lzy[nd]);
lzy[nd << 1 | 1] = max(lzy[nd << 1 | 1], lzy[nd]); }
lzy[nd] = 0; } }
void build(int nd, int le, int ri) {
sgt1[nd] = INF; sgt2[nd] = -1; lzy[nd] = 0;
if (le != ri) {
int md = (le + ri) >> 1;
build(nd << 1, le, md);
build(nd << 1 | 1, md + 1, ri); } }
void update1(int nd, int le, int ri, int ps, int vl) {
updateLazy(nd, le, ri);
if (ri < ps or ps < le) {
return; }
if (le == ri) {
sgt1[nd] = vl; }
else {
int md = (le + ri) >> 1;
update1(nd << 1, le, md, ps, vl);
update1(nd << 1 | 1, md + 1, ri, ps, vl);
sgt1[nd] = min(sgt1[nd << 1], sgt1[nd << 1 | 1]); } }
void update2(int nd, int le, int ri, int st, int en, int vl) {
updateLazy(nd, le, ri);
if (en < le or ri < st) {
return; }
if (st <= le and ri <= en) {
lzy[nd] = max(lzy[nd], vl);
updateLazy(nd, le, ri); }
else {
int md = (le + ri) >> 1;
update2(nd << 1, le, md, st, en, vl);
update2(nd << 1 | 1, md + 1, ri, st, en, vl);
sgt2[nd] = max(sgt2[nd << 1], sgt2[nd << 1 | 1]); } }
int query(int nd, int le, int ri, int st, int en) {
updateLazy(nd, le, ri);
if (en < le or ri < st) {
return -1; }
if (st <= le and ri <= en) {
return sgt2[nd]; }
else {
int md = (le + ri) >> 1;
return max(query(nd << 1, le, md, st, en),
query(nd << 1 | 1, md + 1, ri, st, en)); } }
int main(void) {
#ifdef HOME
freopen("antennas.in", "r", stdin);
freopen("antennas.out", "w", stdout);
#endif
int N; cin >> N;
for (int i = 1; i <= N; ++i) {
cin >> arr[i].h >> arr[i].a >> arr[i].b; }
int Q; cin >> Q;
for (int i = 1; i <= Q; ++i) {
cin >> qry[i].l >> qry[i].r; ans[i] = -1; }
for (int g = 1; g <= 2; ++g) {
for (int i = 1; i <= N; ++i) {
if (i + arr[i].a <= N) {
upd[i + arr[i].a].push_back(i); }
if (i + arr[i].b < N) {
upd[i + arr[i].b + 1].push_back(-i); } }
for (int i = 1; i <= Q; ++i) {
lst[qry[i].r].push_back(i); }
build(1, 1, N);
for (int i = 1; i <= N; ++i) {
for (int x : upd[i]) {
if (x > 0) {
update1(1, 1, N, x, arr[x].h); }
else {
update1(1, 1, N, -x, INF); } }
if (i - arr[i].a >= 1) {
update2(1, 1, N, max(1, i - arr[i].b), i - arr[i].a, arr[i].h); }
for (int x : lst[i]) {
ans[x] = max(ans[x], query(1, 1, N, qry[x].l, qry[x].r)); } }
for (int i = 1; i <= N; ++i) {
upd[i].clear(); lst[i].clear(); }
for (int i = 1, j = N; i <= j; ++i, --j) {
swap(arr[i], arr[j]); }
for (int i = 1; i <= Q; ++i) {
qry[i] = {N - qry[i].r + 1, N - qry[i].l + 1}; } }
for (int i = 1; i <= Q; ++i) {
cout << ans[i] << "\n"; }
return 0; }
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9728 KB |
Output is correct |
2 |
Correct |
10 ms |
9728 KB |
Output is correct |
3 |
Correct |
10 ms |
9728 KB |
Output is correct |
4 |
Correct |
10 ms |
9728 KB |
Output is correct |
5 |
Correct |
10 ms |
9856 KB |
Output is correct |
6 |
Correct |
10 ms |
9728 KB |
Output is correct |
7 |
Correct |
10 ms |
9728 KB |
Output is correct |
8 |
Correct |
10 ms |
9728 KB |
Output is correct |
9 |
Correct |
11 ms |
9728 KB |
Output is correct |
10 |
Correct |
10 ms |
9728 KB |
Output is correct |
11 |
Correct |
10 ms |
9728 KB |
Output is correct |
12 |
Correct |
10 ms |
9856 KB |
Output is correct |
13 |
Correct |
10 ms |
9728 KB |
Output is correct |
14 |
Correct |
10 ms |
9856 KB |
Output is correct |
15 |
Correct |
10 ms |
9728 KB |
Output is correct |
16 |
Correct |
10 ms |
9856 KB |
Output is correct |
17 |
Correct |
10 ms |
9856 KB |
Output is correct |
18 |
Correct |
10 ms |
9856 KB |
Output is correct |
19 |
Correct |
10 ms |
9856 KB |
Output is correct |
20 |
Correct |
9 ms |
9728 KB |
Output is correct |
21 |
Correct |
9 ms |
9728 KB |
Output is correct |
22 |
Correct |
10 ms |
9728 KB |
Output is correct |
23 |
Correct |
9 ms |
9728 KB |
Output is correct |
24 |
Correct |
9 ms |
9728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9728 KB |
Output is correct |
2 |
Correct |
10 ms |
9728 KB |
Output is correct |
3 |
Correct |
10 ms |
9728 KB |
Output is correct |
4 |
Correct |
10 ms |
9728 KB |
Output is correct |
5 |
Correct |
10 ms |
9856 KB |
Output is correct |
6 |
Correct |
10 ms |
9728 KB |
Output is correct |
7 |
Correct |
10 ms |
9728 KB |
Output is correct |
8 |
Correct |
10 ms |
9728 KB |
Output is correct |
9 |
Correct |
11 ms |
9728 KB |
Output is correct |
10 |
Correct |
10 ms |
9728 KB |
Output is correct |
11 |
Correct |
10 ms |
9728 KB |
Output is correct |
12 |
Correct |
10 ms |
9856 KB |
Output is correct |
13 |
Correct |
10 ms |
9728 KB |
Output is correct |
14 |
Correct |
10 ms |
9856 KB |
Output is correct |
15 |
Correct |
10 ms |
9728 KB |
Output is correct |
16 |
Correct |
10 ms |
9856 KB |
Output is correct |
17 |
Correct |
10 ms |
9856 KB |
Output is correct |
18 |
Correct |
10 ms |
9856 KB |
Output is correct |
19 |
Correct |
10 ms |
9856 KB |
Output is correct |
20 |
Correct |
9 ms |
9728 KB |
Output is correct |
21 |
Correct |
9 ms |
9728 KB |
Output is correct |
22 |
Correct |
10 ms |
9728 KB |
Output is correct |
23 |
Correct |
9 ms |
9728 KB |
Output is correct |
24 |
Correct |
9 ms |
9728 KB |
Output is correct |
25 |
Correct |
159 ms |
15096 KB |
Output is correct |
26 |
Correct |
32 ms |
10616 KB |
Output is correct |
27 |
Correct |
271 ms |
17272 KB |
Output is correct |
28 |
Correct |
272 ms |
17400 KB |
Output is correct |
29 |
Correct |
175 ms |
15204 KB |
Output is correct |
30 |
Correct |
164 ms |
14968 KB |
Output is correct |
31 |
Correct |
204 ms |
16504 KB |
Output is correct |
32 |
Correct |
278 ms |
17392 KB |
Output is correct |
33 |
Correct |
253 ms |
17016 KB |
Output is correct |
34 |
Correct |
127 ms |
13468 KB |
Output is correct |
35 |
Correct |
269 ms |
17412 KB |
Output is correct |
36 |
Correct |
272 ms |
17400 KB |
Output is correct |
37 |
Correct |
149 ms |
13688 KB |
Output is correct |
38 |
Correct |
303 ms |
16316 KB |
Output is correct |
39 |
Correct |
42 ms |
10744 KB |
Output is correct |
40 |
Correct |
259 ms |
16376 KB |
Output is correct |
41 |
Correct |
192 ms |
14712 KB |
Output is correct |
42 |
Correct |
272 ms |
16504 KB |
Output is correct |
43 |
Correct |
85 ms |
12152 KB |
Output is correct |
44 |
Correct |
246 ms |
16376 KB |
Output is correct |
45 |
Correct |
51 ms |
11000 KB |
Output is correct |
46 |
Correct |
265 ms |
16484 KB |
Output is correct |
47 |
Correct |
71 ms |
11512 KB |
Output is correct |
48 |
Correct |
263 ms |
16376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
550 ms |
21772 KB |
Output is correct |
2 |
Correct |
615 ms |
22520 KB |
Output is correct |
3 |
Correct |
406 ms |
20548 KB |
Output is correct |
4 |
Correct |
570 ms |
22556 KB |
Output is correct |
5 |
Correct |
238 ms |
15864 KB |
Output is correct |
6 |
Correct |
622 ms |
22444 KB |
Output is correct |
7 |
Correct |
553 ms |
21628 KB |
Output is correct |
8 |
Correct |
596 ms |
22388 KB |
Output is correct |
9 |
Correct |
78 ms |
11624 KB |
Output is correct |
10 |
Correct |
581 ms |
22400 KB |
Output is correct |
11 |
Correct |
318 ms |
16920 KB |
Output is correct |
12 |
Correct |
584 ms |
27000 KB |
Output is correct |
13 |
Correct |
383 ms |
26000 KB |
Output is correct |
14 |
Correct |
377 ms |
25636 KB |
Output is correct |
15 |
Correct |
365 ms |
24880 KB |
Output is correct |
16 |
Correct |
347 ms |
24824 KB |
Output is correct |
17 |
Correct |
389 ms |
26484 KB |
Output is correct |
18 |
Correct |
385 ms |
25208 KB |
Output is correct |
19 |
Correct |
391 ms |
25324 KB |
Output is correct |
20 |
Correct |
390 ms |
25460 KB |
Output is correct |
21 |
Correct |
358 ms |
25636 KB |
Output is correct |
22 |
Correct |
377 ms |
25588 KB |
Output is correct |
23 |
Correct |
372 ms |
25588 KB |
Output is correct |
24 |
Correct |
344 ms |
24568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
9728 KB |
Output is correct |
2 |
Correct |
10 ms |
9728 KB |
Output is correct |
3 |
Correct |
10 ms |
9728 KB |
Output is correct |
4 |
Correct |
10 ms |
9728 KB |
Output is correct |
5 |
Correct |
10 ms |
9856 KB |
Output is correct |
6 |
Correct |
10 ms |
9728 KB |
Output is correct |
7 |
Correct |
10 ms |
9728 KB |
Output is correct |
8 |
Correct |
10 ms |
9728 KB |
Output is correct |
9 |
Correct |
11 ms |
9728 KB |
Output is correct |
10 |
Correct |
10 ms |
9728 KB |
Output is correct |
11 |
Correct |
10 ms |
9728 KB |
Output is correct |
12 |
Correct |
10 ms |
9856 KB |
Output is correct |
13 |
Correct |
10 ms |
9728 KB |
Output is correct |
14 |
Correct |
10 ms |
9856 KB |
Output is correct |
15 |
Correct |
10 ms |
9728 KB |
Output is correct |
16 |
Correct |
10 ms |
9856 KB |
Output is correct |
17 |
Correct |
10 ms |
9856 KB |
Output is correct |
18 |
Correct |
10 ms |
9856 KB |
Output is correct |
19 |
Correct |
10 ms |
9856 KB |
Output is correct |
20 |
Correct |
9 ms |
9728 KB |
Output is correct |
21 |
Correct |
9 ms |
9728 KB |
Output is correct |
22 |
Correct |
10 ms |
9728 KB |
Output is correct |
23 |
Correct |
9 ms |
9728 KB |
Output is correct |
24 |
Correct |
9 ms |
9728 KB |
Output is correct |
25 |
Correct |
159 ms |
15096 KB |
Output is correct |
26 |
Correct |
32 ms |
10616 KB |
Output is correct |
27 |
Correct |
271 ms |
17272 KB |
Output is correct |
28 |
Correct |
272 ms |
17400 KB |
Output is correct |
29 |
Correct |
175 ms |
15204 KB |
Output is correct |
30 |
Correct |
164 ms |
14968 KB |
Output is correct |
31 |
Correct |
204 ms |
16504 KB |
Output is correct |
32 |
Correct |
278 ms |
17392 KB |
Output is correct |
33 |
Correct |
253 ms |
17016 KB |
Output is correct |
34 |
Correct |
127 ms |
13468 KB |
Output is correct |
35 |
Correct |
269 ms |
17412 KB |
Output is correct |
36 |
Correct |
272 ms |
17400 KB |
Output is correct |
37 |
Correct |
149 ms |
13688 KB |
Output is correct |
38 |
Correct |
303 ms |
16316 KB |
Output is correct |
39 |
Correct |
42 ms |
10744 KB |
Output is correct |
40 |
Correct |
259 ms |
16376 KB |
Output is correct |
41 |
Correct |
192 ms |
14712 KB |
Output is correct |
42 |
Correct |
272 ms |
16504 KB |
Output is correct |
43 |
Correct |
85 ms |
12152 KB |
Output is correct |
44 |
Correct |
246 ms |
16376 KB |
Output is correct |
45 |
Correct |
51 ms |
11000 KB |
Output is correct |
46 |
Correct |
265 ms |
16484 KB |
Output is correct |
47 |
Correct |
71 ms |
11512 KB |
Output is correct |
48 |
Correct |
263 ms |
16376 KB |
Output is correct |
49 |
Correct |
550 ms |
21772 KB |
Output is correct |
50 |
Correct |
615 ms |
22520 KB |
Output is correct |
51 |
Correct |
406 ms |
20548 KB |
Output is correct |
52 |
Correct |
570 ms |
22556 KB |
Output is correct |
53 |
Correct |
238 ms |
15864 KB |
Output is correct |
54 |
Correct |
622 ms |
22444 KB |
Output is correct |
55 |
Correct |
553 ms |
21628 KB |
Output is correct |
56 |
Correct |
596 ms |
22388 KB |
Output is correct |
57 |
Correct |
78 ms |
11624 KB |
Output is correct |
58 |
Correct |
581 ms |
22400 KB |
Output is correct |
59 |
Correct |
318 ms |
16920 KB |
Output is correct |
60 |
Correct |
584 ms |
27000 KB |
Output is correct |
61 |
Correct |
383 ms |
26000 KB |
Output is correct |
62 |
Correct |
377 ms |
25636 KB |
Output is correct |
63 |
Correct |
365 ms |
24880 KB |
Output is correct |
64 |
Correct |
347 ms |
24824 KB |
Output is correct |
65 |
Correct |
389 ms |
26484 KB |
Output is correct |
66 |
Correct |
385 ms |
25208 KB |
Output is correct |
67 |
Correct |
391 ms |
25324 KB |
Output is correct |
68 |
Correct |
390 ms |
25460 KB |
Output is correct |
69 |
Correct |
358 ms |
25636 KB |
Output is correct |
70 |
Correct |
377 ms |
25588 KB |
Output is correct |
71 |
Correct |
372 ms |
25588 KB |
Output is correct |
72 |
Correct |
344 ms |
24568 KB |
Output is correct |
73 |
Correct |
943 ms |
35404 KB |
Output is correct |
74 |
Correct |
611 ms |
28280 KB |
Output is correct |
75 |
Correct |
910 ms |
34628 KB |
Output is correct |
76 |
Correct |
1149 ms |
39080 KB |
Output is correct |
77 |
Correct |
596 ms |
25724 KB |
Output is correct |
78 |
Correct |
1047 ms |
35980 KB |
Output is correct |
79 |
Correct |
1097 ms |
37180 KB |
Output is correct |
80 |
Correct |
1191 ms |
38988 KB |
Output is correct |
81 |
Correct |
490 ms |
20728 KB |
Output is correct |
82 |
Correct |
951 ms |
33956 KB |
Output is correct |
83 |
Correct |
873 ms |
30332 KB |
Output is correct |
84 |
Correct |
1204 ms |
39160 KB |
Output is correct |
85 |
Correct |
711 ms |
33448 KB |
Output is correct |
86 |
Correct |
898 ms |
36504 KB |
Output is correct |
87 |
Correct |
466 ms |
27180 KB |
Output is correct |
88 |
Correct |
896 ms |
35768 KB |
Output is correct |
89 |
Correct |
840 ms |
35148 KB |
Output is correct |
90 |
Correct |
952 ms |
36256 KB |
Output is correct |
91 |
Correct |
601 ms |
30444 KB |
Output is correct |
92 |
Correct |
932 ms |
36472 KB |
Output is correct |
93 |
Correct |
480 ms |
28300 KB |
Output is correct |
94 |
Correct |
953 ms |
36616 KB |
Output is correct |
95 |
Correct |
541 ms |
29424 KB |
Output is correct |
96 |
Correct |
921 ms |
35636 KB |
Output is correct |