#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, DEBUG = 0;
scanf("%d", &n);
for (i = 1; i <= n; i++) {
if (!DEBUG) {
scanf("%d%d%d", &w[i].h, &w[i].a, &w[i].b);
}
else {
w[i].h = rand() % 1000;
int b = rand() % n + 1, e = rand() % n + 1;
if (b > e)swap(b, e);
w[i].a = b, w[i].b = e;
}
}
scanf("%d", &Q);
for (i = 1; i <= Q; i++) {
Res[i] = -1;
if (!DEBUG) {
scanf("%d%d", &QQ[i].b, &QQ[i].e);
}
else {
int b = rand() % n + 1, e = rand() % n + 1;
if (b > e)swap(b, e);
QQ[i] = { b,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++) {
if (!DEBUG) {
printf("%d\n", Res[i]);
}
else {
int r = -1;
for (j = QQ[i].b; j <= QQ[i].e; j++) {
for (k = QQ[i].b; k <= QQ[i].e; k++) {
if (max(w[j].a, w[k].a) <= abs(k - j) && abs(k - j) <= min(w[j].b, w[k].b))r = max(r, abs(w[j].h - w[k].h));
}
}
if (r != Res[i]) {
printf("??\n");
}
}
}
}
Compilation message
antennas.cpp: In function 'int main()':
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:110:9: 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:119:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &Q);
~~~~~^~~~~~~~~~
antennas.cpp:123:9: 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 |
21 ms |
15992 KB |
Output is correct |
2 |
Correct |
21 ms |
15992 KB |
Output is correct |
3 |
Correct |
21 ms |
15992 KB |
Output is correct |
4 |
Correct |
18 ms |
15992 KB |
Output is correct |
5 |
Correct |
18 ms |
15992 KB |
Output is correct |
6 |
Correct |
21 ms |
15992 KB |
Output is correct |
7 |
Correct |
18 ms |
15992 KB |
Output is correct |
8 |
Correct |
17 ms |
15992 KB |
Output is correct |
9 |
Correct |
17 ms |
15992 KB |
Output is correct |
10 |
Correct |
18 ms |
15992 KB |
Output is correct |
11 |
Correct |
17 ms |
16040 KB |
Output is correct |
12 |
Correct |
18 ms |
15992 KB |
Output is correct |
13 |
Correct |
17 ms |
15992 KB |
Output is correct |
14 |
Correct |
17 ms |
15992 KB |
Output is correct |
15 |
Correct |
17 ms |
15992 KB |
Output is correct |
16 |
Correct |
17 ms |
15912 KB |
Output is correct |
17 |
Correct |
18 ms |
15992 KB |
Output is correct |
18 |
Correct |
18 ms |
15992 KB |
Output is correct |
19 |
Correct |
17 ms |
15992 KB |
Output is correct |
20 |
Correct |
17 ms |
15992 KB |
Output is correct |
21 |
Correct |
18 ms |
15992 KB |
Output is correct |
22 |
Correct |
18 ms |
15964 KB |
Output is correct |
23 |
Correct |
18 ms |
15992 KB |
Output is correct |
24 |
Correct |
18 ms |
15992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
15992 KB |
Output is correct |
2 |
Correct |
21 ms |
15992 KB |
Output is correct |
3 |
Correct |
21 ms |
15992 KB |
Output is correct |
4 |
Correct |
18 ms |
15992 KB |
Output is correct |
5 |
Correct |
18 ms |
15992 KB |
Output is correct |
6 |
Correct |
21 ms |
15992 KB |
Output is correct |
7 |
Correct |
18 ms |
15992 KB |
Output is correct |
8 |
Correct |
17 ms |
15992 KB |
Output is correct |
9 |
Correct |
17 ms |
15992 KB |
Output is correct |
10 |
Correct |
18 ms |
15992 KB |
Output is correct |
11 |
Correct |
17 ms |
16040 KB |
Output is correct |
12 |
Correct |
18 ms |
15992 KB |
Output is correct |
13 |
Correct |
17 ms |
15992 KB |
Output is correct |
14 |
Correct |
17 ms |
15992 KB |
Output is correct |
15 |
Correct |
17 ms |
15992 KB |
Output is correct |
16 |
Correct |
17 ms |
15912 KB |
Output is correct |
17 |
Correct |
18 ms |
15992 KB |
Output is correct |
18 |
Correct |
18 ms |
15992 KB |
Output is correct |
19 |
Correct |
17 ms |
15992 KB |
Output is correct |
20 |
Correct |
17 ms |
15992 KB |
Output is correct |
21 |
Correct |
18 ms |
15992 KB |
Output is correct |
22 |
Correct |
18 ms |
15964 KB |
Output is correct |
23 |
Correct |
18 ms |
15992 KB |
Output is correct |
24 |
Correct |
18 ms |
15992 KB |
Output is correct |
25 |
Correct |
151 ms |
22536 KB |
Output is correct |
26 |
Correct |
35 ms |
16732 KB |
Output is correct |
27 |
Correct |
215 ms |
25208 KB |
Output is correct |
28 |
Correct |
222 ms |
25080 KB |
Output is correct |
29 |
Correct |
158 ms |
22748 KB |
Output is correct |
30 |
Correct |
153 ms |
22264 KB |
Output is correct |
31 |
Correct |
166 ms |
24184 KB |
Output is correct |
32 |
Correct |
225 ms |
25080 KB |
Output is correct |
33 |
Correct |
203 ms |
24824 KB |
Output is correct |
34 |
Correct |
116 ms |
20344 KB |
Output is correct |
35 |
Correct |
213 ms |
25464 KB |
Output is correct |
36 |
Correct |
224 ms |
25056 KB |
Output is correct |
37 |
Correct |
132 ms |
20732 KB |
Output is correct |
38 |
Correct |
218 ms |
24028 KB |
Output is correct |
39 |
Correct |
46 ms |
17272 KB |
Output is correct |
40 |
Correct |
217 ms |
24184 KB |
Output is correct |
41 |
Correct |
166 ms |
22136 KB |
Output is correct |
42 |
Correct |
217 ms |
24048 KB |
Output is correct |
43 |
Correct |
84 ms |
18808 KB |
Output is correct |
44 |
Correct |
220 ms |
24056 KB |
Output is correct |
45 |
Correct |
53 ms |
17528 KB |
Output is correct |
46 |
Correct |
218 ms |
24056 KB |
Output is correct |
47 |
Correct |
70 ms |
18168 KB |
Output is correct |
48 |
Correct |
219 ms |
24060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
393 ms |
25436 KB |
Output is correct |
2 |
Correct |
437 ms |
25596 KB |
Output is correct |
3 |
Correct |
298 ms |
23924 KB |
Output is correct |
4 |
Correct |
457 ms |
25852 KB |
Output is correct |
5 |
Correct |
183 ms |
21512 KB |
Output is correct |
6 |
Correct |
449 ms |
25800 KB |
Output is correct |
7 |
Correct |
366 ms |
24704 KB |
Output is correct |
8 |
Correct |
484 ms |
25824 KB |
Output is correct |
9 |
Correct |
66 ms |
17912 KB |
Output is correct |
10 |
Correct |
430 ms |
25680 KB |
Output is correct |
11 |
Correct |
249 ms |
23036 KB |
Output is correct |
12 |
Correct |
426 ms |
25576 KB |
Output is correct |
13 |
Correct |
281 ms |
26092 KB |
Output is correct |
14 |
Correct |
262 ms |
28016 KB |
Output is correct |
15 |
Correct |
260 ms |
26612 KB |
Output is correct |
16 |
Correct |
236 ms |
27084 KB |
Output is correct |
17 |
Correct |
289 ms |
28972 KB |
Output is correct |
18 |
Correct |
266 ms |
27848 KB |
Output is correct |
19 |
Correct |
272 ms |
27328 KB |
Output is correct |
20 |
Correct |
270 ms |
27572 KB |
Output is correct |
21 |
Correct |
251 ms |
28124 KB |
Output is correct |
22 |
Correct |
264 ms |
27752 KB |
Output is correct |
23 |
Correct |
268 ms |
27888 KB |
Output is correct |
24 |
Correct |
234 ms |
26340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
15992 KB |
Output is correct |
2 |
Correct |
21 ms |
15992 KB |
Output is correct |
3 |
Correct |
21 ms |
15992 KB |
Output is correct |
4 |
Correct |
18 ms |
15992 KB |
Output is correct |
5 |
Correct |
18 ms |
15992 KB |
Output is correct |
6 |
Correct |
21 ms |
15992 KB |
Output is correct |
7 |
Correct |
18 ms |
15992 KB |
Output is correct |
8 |
Correct |
17 ms |
15992 KB |
Output is correct |
9 |
Correct |
17 ms |
15992 KB |
Output is correct |
10 |
Correct |
18 ms |
15992 KB |
Output is correct |
11 |
Correct |
17 ms |
16040 KB |
Output is correct |
12 |
Correct |
18 ms |
15992 KB |
Output is correct |
13 |
Correct |
17 ms |
15992 KB |
Output is correct |
14 |
Correct |
17 ms |
15992 KB |
Output is correct |
15 |
Correct |
17 ms |
15992 KB |
Output is correct |
16 |
Correct |
17 ms |
15912 KB |
Output is correct |
17 |
Correct |
18 ms |
15992 KB |
Output is correct |
18 |
Correct |
18 ms |
15992 KB |
Output is correct |
19 |
Correct |
17 ms |
15992 KB |
Output is correct |
20 |
Correct |
17 ms |
15992 KB |
Output is correct |
21 |
Correct |
18 ms |
15992 KB |
Output is correct |
22 |
Correct |
18 ms |
15964 KB |
Output is correct |
23 |
Correct |
18 ms |
15992 KB |
Output is correct |
24 |
Correct |
18 ms |
15992 KB |
Output is correct |
25 |
Correct |
151 ms |
22536 KB |
Output is correct |
26 |
Correct |
35 ms |
16732 KB |
Output is correct |
27 |
Correct |
215 ms |
25208 KB |
Output is correct |
28 |
Correct |
222 ms |
25080 KB |
Output is correct |
29 |
Correct |
158 ms |
22748 KB |
Output is correct |
30 |
Correct |
153 ms |
22264 KB |
Output is correct |
31 |
Correct |
166 ms |
24184 KB |
Output is correct |
32 |
Correct |
225 ms |
25080 KB |
Output is correct |
33 |
Correct |
203 ms |
24824 KB |
Output is correct |
34 |
Correct |
116 ms |
20344 KB |
Output is correct |
35 |
Correct |
213 ms |
25464 KB |
Output is correct |
36 |
Correct |
224 ms |
25056 KB |
Output is correct |
37 |
Correct |
132 ms |
20732 KB |
Output is correct |
38 |
Correct |
218 ms |
24028 KB |
Output is correct |
39 |
Correct |
46 ms |
17272 KB |
Output is correct |
40 |
Correct |
217 ms |
24184 KB |
Output is correct |
41 |
Correct |
166 ms |
22136 KB |
Output is correct |
42 |
Correct |
217 ms |
24048 KB |
Output is correct |
43 |
Correct |
84 ms |
18808 KB |
Output is correct |
44 |
Correct |
220 ms |
24056 KB |
Output is correct |
45 |
Correct |
53 ms |
17528 KB |
Output is correct |
46 |
Correct |
218 ms |
24056 KB |
Output is correct |
47 |
Correct |
70 ms |
18168 KB |
Output is correct |
48 |
Correct |
219 ms |
24060 KB |
Output is correct |
49 |
Correct |
393 ms |
25436 KB |
Output is correct |
50 |
Correct |
437 ms |
25596 KB |
Output is correct |
51 |
Correct |
298 ms |
23924 KB |
Output is correct |
52 |
Correct |
457 ms |
25852 KB |
Output is correct |
53 |
Correct |
183 ms |
21512 KB |
Output is correct |
54 |
Correct |
449 ms |
25800 KB |
Output is correct |
55 |
Correct |
366 ms |
24704 KB |
Output is correct |
56 |
Correct |
484 ms |
25824 KB |
Output is correct |
57 |
Correct |
66 ms |
17912 KB |
Output is correct |
58 |
Correct |
430 ms |
25680 KB |
Output is correct |
59 |
Correct |
249 ms |
23036 KB |
Output is correct |
60 |
Correct |
426 ms |
25576 KB |
Output is correct |
61 |
Correct |
281 ms |
26092 KB |
Output is correct |
62 |
Correct |
262 ms |
28016 KB |
Output is correct |
63 |
Correct |
260 ms |
26612 KB |
Output is correct |
64 |
Correct |
236 ms |
27084 KB |
Output is correct |
65 |
Correct |
289 ms |
28972 KB |
Output is correct |
66 |
Correct |
266 ms |
27848 KB |
Output is correct |
67 |
Correct |
272 ms |
27328 KB |
Output is correct |
68 |
Correct |
270 ms |
27572 KB |
Output is correct |
69 |
Correct |
251 ms |
28124 KB |
Output is correct |
70 |
Correct |
264 ms |
27752 KB |
Output is correct |
71 |
Correct |
268 ms |
27888 KB |
Output is correct |
72 |
Correct |
234 ms |
26340 KB |
Output is correct |
73 |
Correct |
703 ms |
37072 KB |
Output is correct |
74 |
Correct |
462 ms |
29628 KB |
Output is correct |
75 |
Correct |
686 ms |
36592 KB |
Output is correct |
76 |
Correct |
910 ms |
41248 KB |
Output is correct |
77 |
Correct |
459 ms |
30064 KB |
Output is correct |
78 |
Correct |
748 ms |
37496 KB |
Output is correct |
79 |
Correct |
822 ms |
39152 KB |
Output is correct |
80 |
Correct |
904 ms |
41056 KB |
Output is correct |
81 |
Correct |
353 ms |
27644 KB |
Output is correct |
82 |
Correct |
668 ms |
35432 KB |
Output is correct |
83 |
Correct |
677 ms |
35316 KB |
Output is correct |
84 |
Correct |
930 ms |
41212 KB |
Output is correct |
85 |
Correct |
548 ms |
35608 KB |
Output is correct |
86 |
Correct |
771 ms |
39676 KB |
Output is correct |
87 |
Correct |
333 ms |
28916 KB |
Output is correct |
88 |
Correct |
682 ms |
38712 KB |
Output is correct |
89 |
Correct |
627 ms |
37748 KB |
Output is correct |
90 |
Correct |
714 ms |
39288 KB |
Output is correct |
91 |
Correct |
435 ms |
32236 KB |
Output is correct |
92 |
Correct |
715 ms |
39384 KB |
Output is correct |
93 |
Correct |
339 ms |
30688 KB |
Output is correct |
94 |
Correct |
741 ms |
39520 KB |
Output is correct |
95 |
Correct |
404 ms |
31532 KB |
Output is correct |
96 |
Correct |
667 ms |
37964 KB |
Output is correct |