#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 = 1000;
vector<iii> block[1000];
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 |
13 ms |
13816 KB |
Output is correct |
2 |
Correct |
15 ms |
13944 KB |
Output is correct |
3 |
Correct |
14 ms |
13816 KB |
Output is correct |
4 |
Correct |
15 ms |
13944 KB |
Output is correct |
5 |
Correct |
14 ms |
13816 KB |
Output is correct |
6 |
Correct |
14 ms |
13944 KB |
Output is correct |
7 |
Correct |
15 ms |
13944 KB |
Output is correct |
8 |
Correct |
15 ms |
13944 KB |
Output is correct |
9 |
Correct |
14 ms |
13816 KB |
Output is correct |
10 |
Correct |
15 ms |
13944 KB |
Output is correct |
11 |
Correct |
14 ms |
13816 KB |
Output is correct |
12 |
Correct |
16 ms |
13944 KB |
Output is correct |
13 |
Correct |
15 ms |
14072 KB |
Output is correct |
14 |
Correct |
14 ms |
13816 KB |
Output is correct |
15 |
Correct |
14 ms |
13948 KB |
Output is correct |
16 |
Correct |
14 ms |
13816 KB |
Output is correct |
17 |
Correct |
15 ms |
13944 KB |
Output is correct |
18 |
Correct |
14 ms |
13944 KB |
Output is correct |
19 |
Correct |
14 ms |
13944 KB |
Output is correct |
20 |
Correct |
14 ms |
13944 KB |
Output is correct |
21 |
Correct |
14 ms |
13948 KB |
Output is correct |
22 |
Correct |
14 ms |
13920 KB |
Output is correct |
23 |
Correct |
14 ms |
13816 KB |
Output is correct |
24 |
Correct |
15 ms |
13816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
13816 KB |
Output is correct |
2 |
Correct |
15 ms |
13944 KB |
Output is correct |
3 |
Correct |
14 ms |
13816 KB |
Output is correct |
4 |
Correct |
15 ms |
13944 KB |
Output is correct |
5 |
Correct |
14 ms |
13816 KB |
Output is correct |
6 |
Correct |
14 ms |
13944 KB |
Output is correct |
7 |
Correct |
15 ms |
13944 KB |
Output is correct |
8 |
Correct |
15 ms |
13944 KB |
Output is correct |
9 |
Correct |
14 ms |
13816 KB |
Output is correct |
10 |
Correct |
15 ms |
13944 KB |
Output is correct |
11 |
Correct |
14 ms |
13816 KB |
Output is correct |
12 |
Correct |
16 ms |
13944 KB |
Output is correct |
13 |
Correct |
15 ms |
14072 KB |
Output is correct |
14 |
Correct |
14 ms |
13816 KB |
Output is correct |
15 |
Correct |
14 ms |
13948 KB |
Output is correct |
16 |
Correct |
14 ms |
13816 KB |
Output is correct |
17 |
Correct |
15 ms |
13944 KB |
Output is correct |
18 |
Correct |
14 ms |
13944 KB |
Output is correct |
19 |
Correct |
14 ms |
13944 KB |
Output is correct |
20 |
Correct |
14 ms |
13944 KB |
Output is correct |
21 |
Correct |
14 ms |
13948 KB |
Output is correct |
22 |
Correct |
14 ms |
13920 KB |
Output is correct |
23 |
Correct |
14 ms |
13816 KB |
Output is correct |
24 |
Correct |
15 ms |
13816 KB |
Output is correct |
25 |
Correct |
2573 ms |
17544 KB |
Output is correct |
26 |
Correct |
530 ms |
15740 KB |
Output is correct |
27 |
Execution timed out |
3046 ms |
18084 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
928 ms |
218096 KB |
Output is correct |
2 |
Correct |
1044 ms |
241904 KB |
Output is correct |
3 |
Correct |
683 ms |
169972 KB |
Output is correct |
4 |
Correct |
1045 ms |
242124 KB |
Output is correct |
5 |
Correct |
443 ms |
113272 KB |
Output is correct |
6 |
Correct |
1027 ms |
241688 KB |
Output is correct |
7 |
Correct |
899 ms |
209996 KB |
Output is correct |
8 |
Correct |
1042 ms |
242032 KB |
Output is correct |
9 |
Correct |
124 ms |
45048 KB |
Output is correct |
10 |
Correct |
1066 ms |
242692 KB |
Output is correct |
11 |
Correct |
601 ms |
151988 KB |
Output is correct |
12 |
Correct |
1012 ms |
241904 KB |
Output is correct |
13 |
Correct |
738 ms |
314108 KB |
Output is correct |
14 |
Correct |
756 ms |
289260 KB |
Output is correct |
15 |
Correct |
603 ms |
259532 KB |
Output is correct |
16 |
Correct |
637 ms |
277772 KB |
Output is correct |
17 |
Correct |
780 ms |
330596 KB |
Output is correct |
18 |
Correct |
663 ms |
287552 KB |
Output is correct |
19 |
Correct |
674 ms |
292748 KB |
Output is correct |
20 |
Correct |
697 ms |
281728 KB |
Output is correct |
21 |
Correct |
659 ms |
275896 KB |
Output is correct |
22 |
Correct |
666 ms |
284292 KB |
Output is correct |
23 |
Correct |
677 ms |
288888 KB |
Output is correct |
24 |
Correct |
609 ms |
267276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
13816 KB |
Output is correct |
2 |
Correct |
15 ms |
13944 KB |
Output is correct |
3 |
Correct |
14 ms |
13816 KB |
Output is correct |
4 |
Correct |
15 ms |
13944 KB |
Output is correct |
5 |
Correct |
14 ms |
13816 KB |
Output is correct |
6 |
Correct |
14 ms |
13944 KB |
Output is correct |
7 |
Correct |
15 ms |
13944 KB |
Output is correct |
8 |
Correct |
15 ms |
13944 KB |
Output is correct |
9 |
Correct |
14 ms |
13816 KB |
Output is correct |
10 |
Correct |
15 ms |
13944 KB |
Output is correct |
11 |
Correct |
14 ms |
13816 KB |
Output is correct |
12 |
Correct |
16 ms |
13944 KB |
Output is correct |
13 |
Correct |
15 ms |
14072 KB |
Output is correct |
14 |
Correct |
14 ms |
13816 KB |
Output is correct |
15 |
Correct |
14 ms |
13948 KB |
Output is correct |
16 |
Correct |
14 ms |
13816 KB |
Output is correct |
17 |
Correct |
15 ms |
13944 KB |
Output is correct |
18 |
Correct |
14 ms |
13944 KB |
Output is correct |
19 |
Correct |
14 ms |
13944 KB |
Output is correct |
20 |
Correct |
14 ms |
13944 KB |
Output is correct |
21 |
Correct |
14 ms |
13948 KB |
Output is correct |
22 |
Correct |
14 ms |
13920 KB |
Output is correct |
23 |
Correct |
14 ms |
13816 KB |
Output is correct |
24 |
Correct |
15 ms |
13816 KB |
Output is correct |
25 |
Correct |
2573 ms |
17544 KB |
Output is correct |
26 |
Correct |
530 ms |
15740 KB |
Output is correct |
27 |
Execution timed out |
3046 ms |
18084 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |