#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define pii pair<int,int>
#define SZ 262144
int n, Q, Res[201000], INF = 1e9+123;
struct point {
int h, a, b;
}w[201000];
struct Query {
int b, e;
}QQ[201000];
vector<pii>G[201000], A[201000];
struct Tree {
int Mx[SZ + SZ], MnC[SZ + SZ], MxH[SZ + SZ];
void init() {
for (int i = 0; i < SZ + SZ; i++) {
Mx[i] = -INF;
MxH[i] = -INF;
MnC[i] = INF;
}
}
void Spread(int nd) {
Mx[nd * 2] = max(Mx[nd * 2], MxH[nd] - MnC[nd * 2]);
MxH[nd * 2] = max(MxH[nd * 2], MxH[nd]);
Mx[nd * 2 + 1] = max(Mx[nd * 2 + 1], MxH[nd] - MnC[nd * 2 + 1]);
MxH[nd * 2 + 1] = max(MxH[nd * 2 + 1], MxH[nd]);
Mx[nd] = max(Mx[nd], max(Mx[nd * 2], Mx[nd * 2 + 1]));
MxH[nd] = -INF;
}
void UDT(int nd) {
MnC[nd] = min(MnC[nd * 2], MnC[nd * 2 + 1]);
Mx[nd] = max(Mx[nd * 2], Mx[nd * 2 + 1]);
}
void PutC(int nd, int b, int e, int x, int c) {
if (b == e) {
MnC[nd] = c;
return;
}
Spread(nd);
int m = (b + e) >> 1;
if (x <= m)PutC(nd * 2, b, m, x, c);
else PutC(nd * 2 + 1, m + 1, e, x, c);
UDT(nd);
}
void Do(int nd, int b, int e, int s, int l, int h) {
if (s > l)return;
if (s <= b && e <= l) {
if(b!=e) Spread(nd);
MxH[nd] = h;
Mx[nd] = max(Mx[nd], h - MnC[nd]);
return;
}
Spread(nd);
int m = (b + e) >> 1;
if (s <= m)Do(nd * 2, b, m, s, l, h);
if(l > m) Do(nd * 2 + 1, m + 1, e, s, l, h);
UDT(nd);
}
int Get(int nd, int b, int e, int s, int l) {
if (s > l)return -INF;
if (s <= b && e <= l)return Mx[nd];
Spread(nd);
int m = (b + e) >> 1, r = -INF;
if (s <= m)r = max(r, Get(nd * 2, b, m, s, l));
if (l > m) r = max(r, Get(nd * 2 + 1, m + 1, e, s, l));
UDT(nd);
return r;
}
}T;
void Solve() {
int i;
for (i = 1; i <= n; i++) {
G[i].clear();
A[i].clear();
}
T.init();
for (i = 1; i <= Q; i++) {
G[QQ[i].e].push_back({ QQ[i].b,i });
}
for (i = 1; i <= n; i++) {
int b = i + w[i].a;
int e = min(i + w[i].b, n);
if (b > e)continue;
A[b].push_back({ i,1 });
A[e + 1].push_back({ i,-1 });
}
for (i = 1; i <= n; i++) {
for (auto &t : A[i]) {
if (t.second == 1)T.PutC(1, 1, n, t.first, w[t.first].h);
else T.PutC(1, 1, n, t.first, INF);
}
int b = max(i - w[i].b, 1), e = i - w[i].a;
if (b <= e) T.Do(1, 1, n, b, e, w[i].h);
for (auto &t : G[i]) {
int b = t.first;
Res[t.second] = max(Res[t.second], T.Get(1, 1, n, b, i - 1));
}
}
}
int main() {
int i, j, k;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
scanf("%d%d%d", &w[i].h, &w[i].a, &w[i].b);
}
scanf("%d", &Q);
for (i = 1; i <= Q; i++) {
Res[i] = -1;
scanf("%d%d", &QQ[i].b, &QQ[i].e);
}
Solve();
reverse(w + 1, w + n + 1);
for (i = 1; i <= Q; i++) {
int b = QQ[i].b, e = QQ[i].e;
QQ[i].b = n - e + 1, QQ[i].e = n - b + 1;
}
Solve();
for (i = 1; i <= Q; i++) {
printf("%d\n", Res[i]);
}
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:106:9: warning: unused variable 'j' [-Wunused-variable]
int i, j, k;
^
antennas.cpp:106:12: warning: unused variable 'k' [-Wunused-variable]
int i, j, k;
^
antennas.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
antennas.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &w[i].h, &w[i].a, &w[i].b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
antennas.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &QQ[i].b, &QQ[i].e);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
15992 KB |
Output is correct |
2 |
Correct |
18 ms |
15992 KB |
Output is correct |
3 |
Correct |
18 ms |
15864 KB |
Output is correct |
4 |
Correct |
17 ms |
15992 KB |
Output is correct |
5 |
Correct |
17 ms |
15864 KB |
Output is correct |
6 |
Correct |
17 ms |
15992 KB |
Output is correct |
7 |
Correct |
17 ms |
15992 KB |
Output is correct |
8 |
Correct |
18 ms |
15868 KB |
Output is correct |
9 |
Correct |
18 ms |
16120 KB |
Output is correct |
10 |
Correct |
25 ms |
15864 KB |
Output is correct |
11 |
Correct |
18 ms |
15992 KB |
Output is correct |
12 |
Correct |
20 ms |
15992 KB |
Output is correct |
13 |
Correct |
20 ms |
15992 KB |
Output is correct |
14 |
Correct |
21 ms |
15996 KB |
Output is correct |
15 |
Correct |
21 ms |
15992 KB |
Output is correct |
16 |
Correct |
17 ms |
15864 KB |
Output is correct |
17 |
Correct |
17 ms |
15992 KB |
Output is correct |
18 |
Correct |
18 ms |
15992 KB |
Output is correct |
19 |
Correct |
20 ms |
15992 KB |
Output is correct |
20 |
Correct |
18 ms |
15992 KB |
Output is correct |
21 |
Correct |
18 ms |
15996 KB |
Output is correct |
22 |
Correct |
20 ms |
15864 KB |
Output is correct |
23 |
Correct |
17 ms |
15992 KB |
Output is correct |
24 |
Correct |
18 ms |
15992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
15992 KB |
Output is correct |
2 |
Correct |
18 ms |
15992 KB |
Output is correct |
3 |
Correct |
18 ms |
15864 KB |
Output is correct |
4 |
Correct |
17 ms |
15992 KB |
Output is correct |
5 |
Correct |
17 ms |
15864 KB |
Output is correct |
6 |
Correct |
17 ms |
15992 KB |
Output is correct |
7 |
Correct |
17 ms |
15992 KB |
Output is correct |
8 |
Correct |
18 ms |
15868 KB |
Output is correct |
9 |
Correct |
18 ms |
16120 KB |
Output is correct |
10 |
Correct |
25 ms |
15864 KB |
Output is correct |
11 |
Correct |
18 ms |
15992 KB |
Output is correct |
12 |
Correct |
20 ms |
15992 KB |
Output is correct |
13 |
Correct |
20 ms |
15992 KB |
Output is correct |
14 |
Correct |
21 ms |
15996 KB |
Output is correct |
15 |
Correct |
21 ms |
15992 KB |
Output is correct |
16 |
Correct |
17 ms |
15864 KB |
Output is correct |
17 |
Correct |
17 ms |
15992 KB |
Output is correct |
18 |
Correct |
18 ms |
15992 KB |
Output is correct |
19 |
Correct |
20 ms |
15992 KB |
Output is correct |
20 |
Correct |
18 ms |
15992 KB |
Output is correct |
21 |
Correct |
18 ms |
15996 KB |
Output is correct |
22 |
Correct |
20 ms |
15864 KB |
Output is correct |
23 |
Correct |
17 ms |
15992 KB |
Output is correct |
24 |
Correct |
18 ms |
15992 KB |
Output is correct |
25 |
Correct |
166 ms |
21408 KB |
Output is correct |
26 |
Correct |
36 ms |
16632 KB |
Output is correct |
27 |
Correct |
218 ms |
23536 KB |
Output is correct |
28 |
Correct |
221 ms |
23288 KB |
Output is correct |
29 |
Correct |
152 ms |
21496 KB |
Output is correct |
30 |
Correct |
155 ms |
21036 KB |
Output is correct |
31 |
Correct |
170 ms |
22684 KB |
Output is correct |
32 |
Correct |
250 ms |
23152 KB |
Output is correct |
33 |
Correct |
201 ms |
23160 KB |
Output is correct |
34 |
Correct |
116 ms |
19472 KB |
Output is correct |
35 |
Correct |
214 ms |
23672 KB |
Output is correct |
36 |
Correct |
229 ms |
23156 KB |
Output is correct |
37 |
Correct |
142 ms |
19728 KB |
Output is correct |
38 |
Correct |
222 ms |
22264 KB |
Output is correct |
39 |
Correct |
51 ms |
16888 KB |
Output is correct |
40 |
Correct |
219 ms |
22136 KB |
Output is correct |
41 |
Correct |
164 ms |
20856 KB |
Output is correct |
42 |
Correct |
221 ms |
22136 KB |
Output is correct |
43 |
Correct |
85 ms |
18296 KB |
Output is correct |
44 |
Correct |
216 ms |
22136 KB |
Output is correct |
45 |
Correct |
52 ms |
17144 KB |
Output is correct |
46 |
Correct |
223 ms |
22180 KB |
Output is correct |
47 |
Correct |
69 ms |
17656 KB |
Output is correct |
48 |
Correct |
217 ms |
22264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
387 ms |
23048 KB |
Output is correct |
2 |
Correct |
433 ms |
23804 KB |
Output is correct |
3 |
Correct |
282 ms |
21872 KB |
Output is correct |
4 |
Correct |
436 ms |
23800 KB |
Output is correct |
5 |
Correct |
182 ms |
19568 KB |
Output is correct |
6 |
Correct |
432 ms |
23656 KB |
Output is correct |
7 |
Correct |
369 ms |
22768 KB |
Output is correct |
8 |
Correct |
422 ms |
23772 KB |
Output is correct |
9 |
Correct |
63 ms |
17144 KB |
Output is correct |
10 |
Correct |
437 ms |
23660 KB |
Output is correct |
11 |
Correct |
252 ms |
20720 KB |
Output is correct |
12 |
Correct |
432 ms |
23752 KB |
Output is correct |
13 |
Correct |
278 ms |
24156 KB |
Output is correct |
14 |
Correct |
262 ms |
23648 KB |
Output is correct |
15 |
Correct |
260 ms |
22216 KB |
Output is correct |
16 |
Correct |
236 ms |
22636 KB |
Output is correct |
17 |
Correct |
289 ms |
24588 KB |
Output is correct |
18 |
Correct |
266 ms |
23492 KB |
Output is correct |
19 |
Correct |
270 ms |
22892 KB |
Output is correct |
20 |
Correct |
271 ms |
23272 KB |
Output is correct |
21 |
Correct |
246 ms |
23620 KB |
Output is correct |
22 |
Correct |
264 ms |
23324 KB |
Output is correct |
23 |
Correct |
267 ms |
23344 KB |
Output is correct |
24 |
Correct |
231 ms |
21748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
15992 KB |
Output is correct |
2 |
Correct |
18 ms |
15992 KB |
Output is correct |
3 |
Correct |
18 ms |
15864 KB |
Output is correct |
4 |
Correct |
17 ms |
15992 KB |
Output is correct |
5 |
Correct |
17 ms |
15864 KB |
Output is correct |
6 |
Correct |
17 ms |
15992 KB |
Output is correct |
7 |
Correct |
17 ms |
15992 KB |
Output is correct |
8 |
Correct |
18 ms |
15868 KB |
Output is correct |
9 |
Correct |
18 ms |
16120 KB |
Output is correct |
10 |
Correct |
25 ms |
15864 KB |
Output is correct |
11 |
Correct |
18 ms |
15992 KB |
Output is correct |
12 |
Correct |
20 ms |
15992 KB |
Output is correct |
13 |
Correct |
20 ms |
15992 KB |
Output is correct |
14 |
Correct |
21 ms |
15996 KB |
Output is correct |
15 |
Correct |
21 ms |
15992 KB |
Output is correct |
16 |
Correct |
17 ms |
15864 KB |
Output is correct |
17 |
Correct |
17 ms |
15992 KB |
Output is correct |
18 |
Correct |
18 ms |
15992 KB |
Output is correct |
19 |
Correct |
20 ms |
15992 KB |
Output is correct |
20 |
Correct |
18 ms |
15992 KB |
Output is correct |
21 |
Correct |
18 ms |
15996 KB |
Output is correct |
22 |
Correct |
20 ms |
15864 KB |
Output is correct |
23 |
Correct |
17 ms |
15992 KB |
Output is correct |
24 |
Correct |
18 ms |
15992 KB |
Output is correct |
25 |
Correct |
166 ms |
21408 KB |
Output is correct |
26 |
Correct |
36 ms |
16632 KB |
Output is correct |
27 |
Correct |
218 ms |
23536 KB |
Output is correct |
28 |
Correct |
221 ms |
23288 KB |
Output is correct |
29 |
Correct |
152 ms |
21496 KB |
Output is correct |
30 |
Correct |
155 ms |
21036 KB |
Output is correct |
31 |
Correct |
170 ms |
22684 KB |
Output is correct |
32 |
Correct |
250 ms |
23152 KB |
Output is correct |
33 |
Correct |
201 ms |
23160 KB |
Output is correct |
34 |
Correct |
116 ms |
19472 KB |
Output is correct |
35 |
Correct |
214 ms |
23672 KB |
Output is correct |
36 |
Correct |
229 ms |
23156 KB |
Output is correct |
37 |
Correct |
142 ms |
19728 KB |
Output is correct |
38 |
Correct |
222 ms |
22264 KB |
Output is correct |
39 |
Correct |
51 ms |
16888 KB |
Output is correct |
40 |
Correct |
219 ms |
22136 KB |
Output is correct |
41 |
Correct |
164 ms |
20856 KB |
Output is correct |
42 |
Correct |
221 ms |
22136 KB |
Output is correct |
43 |
Correct |
85 ms |
18296 KB |
Output is correct |
44 |
Correct |
216 ms |
22136 KB |
Output is correct |
45 |
Correct |
52 ms |
17144 KB |
Output is correct |
46 |
Correct |
223 ms |
22180 KB |
Output is correct |
47 |
Correct |
69 ms |
17656 KB |
Output is correct |
48 |
Correct |
217 ms |
22264 KB |
Output is correct |
49 |
Correct |
387 ms |
23048 KB |
Output is correct |
50 |
Correct |
433 ms |
23804 KB |
Output is correct |
51 |
Correct |
282 ms |
21872 KB |
Output is correct |
52 |
Correct |
436 ms |
23800 KB |
Output is correct |
53 |
Correct |
182 ms |
19568 KB |
Output is correct |
54 |
Correct |
432 ms |
23656 KB |
Output is correct |
55 |
Correct |
369 ms |
22768 KB |
Output is correct |
56 |
Correct |
422 ms |
23772 KB |
Output is correct |
57 |
Correct |
63 ms |
17144 KB |
Output is correct |
58 |
Correct |
437 ms |
23660 KB |
Output is correct |
59 |
Correct |
252 ms |
20720 KB |
Output is correct |
60 |
Correct |
432 ms |
23752 KB |
Output is correct |
61 |
Correct |
278 ms |
24156 KB |
Output is correct |
62 |
Correct |
262 ms |
23648 KB |
Output is correct |
63 |
Correct |
260 ms |
22216 KB |
Output is correct |
64 |
Correct |
236 ms |
22636 KB |
Output is correct |
65 |
Correct |
289 ms |
24588 KB |
Output is correct |
66 |
Correct |
266 ms |
23492 KB |
Output is correct |
67 |
Correct |
270 ms |
22892 KB |
Output is correct |
68 |
Correct |
271 ms |
23272 KB |
Output is correct |
69 |
Correct |
246 ms |
23620 KB |
Output is correct |
70 |
Correct |
264 ms |
23324 KB |
Output is correct |
71 |
Correct |
267 ms |
23344 KB |
Output is correct |
72 |
Correct |
231 ms |
21748 KB |
Output is correct |
73 |
Correct |
723 ms |
30912 KB |
Output is correct |
74 |
Correct |
465 ms |
24896 KB |
Output is correct |
75 |
Correct |
686 ms |
30868 KB |
Output is correct |
76 |
Correct |
873 ms |
33980 KB |
Output is correct |
77 |
Correct |
469 ms |
26332 KB |
Output is correct |
78 |
Correct |
746 ms |
31184 KB |
Output is correct |
79 |
Correct |
807 ms |
32560 KB |
Output is correct |
80 |
Correct |
906 ms |
33956 KB |
Output is correct |
81 |
Correct |
371 ms |
24852 KB |
Output is correct |
82 |
Correct |
652 ms |
29560 KB |
Output is correct |
83 |
Correct |
642 ms |
30040 KB |
Output is correct |
84 |
Correct |
865 ms |
34076 KB |
Output is correct |
85 |
Correct |
547 ms |
29800 KB |
Output is correct |
86 |
Correct |
710 ms |
32656 KB |
Output is correct |
87 |
Correct |
331 ms |
24052 KB |
Output is correct |
88 |
Correct |
685 ms |
31768 KB |
Output is correct |
89 |
Correct |
625 ms |
31508 KB |
Output is correct |
90 |
Correct |
715 ms |
32252 KB |
Output is correct |
91 |
Correct |
428 ms |
26960 KB |
Output is correct |
92 |
Correct |
719 ms |
32232 KB |
Output is correct |
93 |
Correct |
335 ms |
25948 KB |
Output is correct |
94 |
Correct |
723 ms |
32572 KB |
Output is correct |
95 |
Correct |
394 ms |
26608 KB |
Output is correct |
96 |
Correct |
663 ms |
30948 KB |
Output is correct |