#include <bits/stdc++.h>
#define iii tuple<int, int, int>
using namespace std;
const int N = 1<<18;
const int INF = 1e9+1;
int n, m;
int H[N], x[N], y[N];
vector<int> preadd[N], predel[N];
struct node {
int mn, mx;
node *l, *r;
node(int mn, int mx, node *l, node *r) : mn(mn), mx(mx), l(l), r(r) {}
};
node* newson(int mn, int mx) { return new node(mn, mx, nullptr, nullptr); }
node * newpar(node *l, node *r) { return new node(min(l->mn, r->mn), max(l->mx, r->mx), l, r); }
node* build(int l = 1, int r = n) {
if(l == r) return newson(INF, -INF);
int m = (l + r) >> 1;
return newpar(build(l, m), build(m+1, r));
}
node* update(int v, bool st, node* p, int l = 1, int r = n) {
if(l == r) {
if(st) return newson(H[v], H[v]);
return newson(INF, -INF);
}
int m = (l + r) >> 1;
if(v <= m) return newpar(update(v, st, p->l, l, m), p->r);
return newpar(p->l, update(v, st, p->r, m+1, r));
}
int qmin(int x, int y, node* p, int l = 1, int r = n) {
if(x > r || l > y) return INF;
if(x <= l && r <= y) return p->mn;
int m = (l + r) >> 1;
return min(qmin(x, y, p->l, l, m), qmin(x, y, p->r, m+1, r));
}
int qmax(int x, int y, node* p, int l = 1, int r = n) {
if(x > r || l > y) return -INF;
if(x <= l && r <= y) return p-> mx;
int m = (l + r) >> 1;
return max(qmax(x, y, p->l, l, m), qmax(x, y, p->r, m+1, r));
}
node *ver[N];
int ans[N];
const int sz = 50;
vector<iii> block[10000];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d %d %d", H+i, x+i, y+i);
if(i + x[i] <= n) preadd[i+x[i]].emplace_back(i), predel[min(n, i+y[i]) + 1].emplace_back(i);
if(i - x[i] >= 1) preadd[max(1, i-y[i])].emplace_back(i), predel[i-x[i] + 1].emplace_back(i);
}
ver[0] = ver[1] = build();
for(int i = 1; i <= n; ++i) {
for(int v : preadd[i]) ver[i] = update(v, true, ver[i]);//, cerr << "add -> " << i << ' ' << v << endl;
for(int v : predel[i]) ver[i] = update(v, false, ver[i]);//, cerr << "del -> " << i << ' ' << v << endl;
ver[i+1] = ver[i];
}
scanf("%d", &m);
memset(ans, -1, sizeof ans);
for(int i = 0, l, r; i < m; ++i) {
scanf("%d %d", &l, &r);
block[l / sz].emplace_back(r, l, i);
}
for(int i = 0; i < sz; ++i) {
sort(block[i].begin(), block[i].end());
int pa = (i+1) * sz;
int pmx = -1, ptr = pa;
for(auto z : block[i]) {
int l, r, idx; tie(r, l, idx) = z;
// cerr << l << ' ' << r << endl;
int imx = -1;
while(ptr <= r) {
pmx = max({pmx, H[ptr] - qmin(max(pa, ptr - y[ptr]), ptr - x[ptr], ver[ptr]), qmax(max(pa, ptr - y[ptr]), ptr - x[ptr], ver[ptr]) - H[ptr]});
ptr++;
}
for(int i = min(r, pa-1); i >= l; --i) {
imx = max({imx, H[i] - qmin(i+x[i], min(r, i+y[i]), ver[i]), qmax(i+x[i], min(r, i+y[i]), ver[i]) - H[i]});
}
ans[idx] = max(pmx, imx);
}
}
for(int i = 0; i < m; ++i) printf("%d\n", ans[i]);
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
antennas.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", H+i, x+i, y+i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &m);
~~~~~^~~~~~~~~~
antennas.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &l, &r);
~~~~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
13944 KB |
Output is correct |
2 |
Correct |
17 ms |
14072 KB |
Output is correct |
3 |
Correct |
14 ms |
14072 KB |
Output is correct |
4 |
Correct |
16 ms |
14072 KB |
Output is correct |
5 |
Correct |
14 ms |
14072 KB |
Output is correct |
6 |
Correct |
14 ms |
14072 KB |
Output is correct |
7 |
Correct |
15 ms |
14072 KB |
Output is correct |
8 |
Correct |
15 ms |
14072 KB |
Output is correct |
9 |
Correct |
14 ms |
13944 KB |
Output is correct |
10 |
Correct |
14 ms |
14072 KB |
Output is correct |
11 |
Correct |
13 ms |
13944 KB |
Output is correct |
12 |
Correct |
15 ms |
14072 KB |
Output is correct |
13 |
Correct |
14 ms |
14072 KB |
Output is correct |
14 |
Correct |
14 ms |
14072 KB |
Output is correct |
15 |
Correct |
15 ms |
14072 KB |
Output is correct |
16 |
Correct |
15 ms |
14072 KB |
Output is correct |
17 |
Correct |
14 ms |
14072 KB |
Output is correct |
18 |
Correct |
14 ms |
14072 KB |
Output is correct |
19 |
Correct |
15 ms |
14072 KB |
Output is correct |
20 |
Correct |
14 ms |
14072 KB |
Output is correct |
21 |
Correct |
14 ms |
14072 KB |
Output is correct |
22 |
Correct |
14 ms |
14072 KB |
Output is correct |
23 |
Correct |
14 ms |
14044 KB |
Output is correct |
24 |
Correct |
14 ms |
14072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
13944 KB |
Output is correct |
2 |
Correct |
17 ms |
14072 KB |
Output is correct |
3 |
Correct |
14 ms |
14072 KB |
Output is correct |
4 |
Correct |
16 ms |
14072 KB |
Output is correct |
5 |
Correct |
14 ms |
14072 KB |
Output is correct |
6 |
Correct |
14 ms |
14072 KB |
Output is correct |
7 |
Correct |
15 ms |
14072 KB |
Output is correct |
8 |
Correct |
15 ms |
14072 KB |
Output is correct |
9 |
Correct |
14 ms |
13944 KB |
Output is correct |
10 |
Correct |
14 ms |
14072 KB |
Output is correct |
11 |
Correct |
13 ms |
13944 KB |
Output is correct |
12 |
Correct |
15 ms |
14072 KB |
Output is correct |
13 |
Correct |
14 ms |
14072 KB |
Output is correct |
14 |
Correct |
14 ms |
14072 KB |
Output is correct |
15 |
Correct |
15 ms |
14072 KB |
Output is correct |
16 |
Correct |
15 ms |
14072 KB |
Output is correct |
17 |
Correct |
14 ms |
14072 KB |
Output is correct |
18 |
Correct |
14 ms |
14072 KB |
Output is correct |
19 |
Correct |
15 ms |
14072 KB |
Output is correct |
20 |
Correct |
14 ms |
14072 KB |
Output is correct |
21 |
Correct |
14 ms |
14072 KB |
Output is correct |
22 |
Correct |
14 ms |
14072 KB |
Output is correct |
23 |
Correct |
14 ms |
14044 KB |
Output is correct |
24 |
Correct |
14 ms |
14072 KB |
Output is correct |
25 |
Correct |
338 ms |
18364 KB |
Output is correct |
26 |
Correct |
65 ms |
15864 KB |
Output is correct |
27 |
Correct |
494 ms |
20060 KB |
Output is correct |
28 |
Correct |
516 ms |
20732 KB |
Output is correct |
29 |
Correct |
337 ms |
17844 KB |
Output is correct |
30 |
Correct |
352 ms |
18552 KB |
Output is correct |
31 |
Correct |
347 ms |
18024 KB |
Output is correct |
32 |
Correct |
547 ms |
20600 KB |
Output is correct |
33 |
Correct |
436 ms |
18936 KB |
Output is correct |
34 |
Correct |
261 ms |
18040 KB |
Output is correct |
35 |
Correct |
471 ms |
19704 KB |
Output is correct |
36 |
Correct |
513 ms |
20856 KB |
Output is correct |
37 |
Correct |
184 ms |
17912 KB |
Output is correct |
38 |
Correct |
462 ms |
19960 KB |
Output is correct |
39 |
Correct |
67 ms |
16248 KB |
Output is correct |
40 |
Correct |
390 ms |
19952 KB |
Output is correct |
41 |
Correct |
254 ms |
18268 KB |
Output is correct |
42 |
Correct |
392 ms |
20128 KB |
Output is correct |
43 |
Correct |
113 ms |
16760 KB |
Output is correct |
44 |
Correct |
353 ms |
20060 KB |
Output is correct |
45 |
Correct |
70 ms |
16248 KB |
Output is correct |
46 |
Correct |
348 ms |
19736 KB |
Output is correct |
47 |
Correct |
93 ms |
16632 KB |
Output is correct |
48 |
Correct |
400 ms |
19960 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
921 ms |
218096 KB |
Output is correct |
2 |
Correct |
1038 ms |
242032 KB |
Output is correct |
3 |
Correct |
667 ms |
170228 KB |
Output is correct |
4 |
Correct |
1016 ms |
242412 KB |
Output is correct |
5 |
Correct |
398 ms |
113400 KB |
Output is correct |
6 |
Correct |
1069 ms |
241708 KB |
Output is correct |
7 |
Correct |
1079 ms |
210000 KB |
Output is correct |
8 |
Correct |
1026 ms |
242248 KB |
Output is correct |
9 |
Correct |
123 ms |
45304 KB |
Output is correct |
10 |
Correct |
1035 ms |
242820 KB |
Output is correct |
11 |
Correct |
588 ms |
152028 KB |
Output is correct |
12 |
Correct |
1022 ms |
242176 KB |
Output is correct |
13 |
Correct |
739 ms |
314124 KB |
Output is correct |
14 |
Correct |
683 ms |
289364 KB |
Output is correct |
15 |
Correct |
605 ms |
259600 KB |
Output is correct |
16 |
Correct |
642 ms |
277996 KB |
Output is correct |
17 |
Correct |
784 ms |
330688 KB |
Output is correct |
18 |
Correct |
661 ms |
287828 KB |
Output is correct |
19 |
Correct |
677 ms |
293004 KB |
Output is correct |
20 |
Correct |
658 ms |
281764 KB |
Output is correct |
21 |
Correct |
656 ms |
276072 KB |
Output is correct |
22 |
Correct |
668 ms |
284312 KB |
Output is correct |
23 |
Correct |
673 ms |
288960 KB |
Output is correct |
24 |
Correct |
602 ms |
267428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
13944 KB |
Output is correct |
2 |
Correct |
17 ms |
14072 KB |
Output is correct |
3 |
Correct |
14 ms |
14072 KB |
Output is correct |
4 |
Correct |
16 ms |
14072 KB |
Output is correct |
5 |
Correct |
14 ms |
14072 KB |
Output is correct |
6 |
Correct |
14 ms |
14072 KB |
Output is correct |
7 |
Correct |
15 ms |
14072 KB |
Output is correct |
8 |
Correct |
15 ms |
14072 KB |
Output is correct |
9 |
Correct |
14 ms |
13944 KB |
Output is correct |
10 |
Correct |
14 ms |
14072 KB |
Output is correct |
11 |
Correct |
13 ms |
13944 KB |
Output is correct |
12 |
Correct |
15 ms |
14072 KB |
Output is correct |
13 |
Correct |
14 ms |
14072 KB |
Output is correct |
14 |
Correct |
14 ms |
14072 KB |
Output is correct |
15 |
Correct |
15 ms |
14072 KB |
Output is correct |
16 |
Correct |
15 ms |
14072 KB |
Output is correct |
17 |
Correct |
14 ms |
14072 KB |
Output is correct |
18 |
Correct |
14 ms |
14072 KB |
Output is correct |
19 |
Correct |
15 ms |
14072 KB |
Output is correct |
20 |
Correct |
14 ms |
14072 KB |
Output is correct |
21 |
Correct |
14 ms |
14072 KB |
Output is correct |
22 |
Correct |
14 ms |
14072 KB |
Output is correct |
23 |
Correct |
14 ms |
14044 KB |
Output is correct |
24 |
Correct |
14 ms |
14072 KB |
Output is correct |
25 |
Correct |
338 ms |
18364 KB |
Output is correct |
26 |
Correct |
65 ms |
15864 KB |
Output is correct |
27 |
Correct |
494 ms |
20060 KB |
Output is correct |
28 |
Correct |
516 ms |
20732 KB |
Output is correct |
29 |
Correct |
337 ms |
17844 KB |
Output is correct |
30 |
Correct |
352 ms |
18552 KB |
Output is correct |
31 |
Correct |
347 ms |
18024 KB |
Output is correct |
32 |
Correct |
547 ms |
20600 KB |
Output is correct |
33 |
Correct |
436 ms |
18936 KB |
Output is correct |
34 |
Correct |
261 ms |
18040 KB |
Output is correct |
35 |
Correct |
471 ms |
19704 KB |
Output is correct |
36 |
Correct |
513 ms |
20856 KB |
Output is correct |
37 |
Correct |
184 ms |
17912 KB |
Output is correct |
38 |
Correct |
462 ms |
19960 KB |
Output is correct |
39 |
Correct |
67 ms |
16248 KB |
Output is correct |
40 |
Correct |
390 ms |
19952 KB |
Output is correct |
41 |
Correct |
254 ms |
18268 KB |
Output is correct |
42 |
Correct |
392 ms |
20128 KB |
Output is correct |
43 |
Correct |
113 ms |
16760 KB |
Output is correct |
44 |
Correct |
353 ms |
20060 KB |
Output is correct |
45 |
Correct |
70 ms |
16248 KB |
Output is correct |
46 |
Correct |
348 ms |
19736 KB |
Output is correct |
47 |
Correct |
93 ms |
16632 KB |
Output is correct |
48 |
Correct |
400 ms |
19960 KB |
Output is correct |
49 |
Correct |
921 ms |
218096 KB |
Output is correct |
50 |
Correct |
1038 ms |
242032 KB |
Output is correct |
51 |
Correct |
667 ms |
170228 KB |
Output is correct |
52 |
Correct |
1016 ms |
242412 KB |
Output is correct |
53 |
Correct |
398 ms |
113400 KB |
Output is correct |
54 |
Correct |
1069 ms |
241708 KB |
Output is correct |
55 |
Correct |
1079 ms |
210000 KB |
Output is correct |
56 |
Correct |
1026 ms |
242248 KB |
Output is correct |
57 |
Correct |
123 ms |
45304 KB |
Output is correct |
58 |
Correct |
1035 ms |
242820 KB |
Output is correct |
59 |
Correct |
588 ms |
152028 KB |
Output is correct |
60 |
Correct |
1022 ms |
242176 KB |
Output is correct |
61 |
Correct |
739 ms |
314124 KB |
Output is correct |
62 |
Correct |
683 ms |
289364 KB |
Output is correct |
63 |
Correct |
605 ms |
259600 KB |
Output is correct |
64 |
Correct |
642 ms |
277996 KB |
Output is correct |
65 |
Correct |
784 ms |
330688 KB |
Output is correct |
66 |
Correct |
661 ms |
287828 KB |
Output is correct |
67 |
Correct |
677 ms |
293004 KB |
Output is correct |
68 |
Correct |
658 ms |
281764 KB |
Output is correct |
69 |
Correct |
656 ms |
276072 KB |
Output is correct |
70 |
Correct |
668 ms |
284312 KB |
Output is correct |
71 |
Correct |
673 ms |
288960 KB |
Output is correct |
72 |
Correct |
602 ms |
267428 KB |
Output is correct |
73 |
Execution timed out |
3020 ms |
220944 KB |
Time limit exceeded |
74 |
Halted |
0 ms |
0 KB |
- |