#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <iomanip>
#include <cassert>
#include <deque>
#include <functional>
#include <set>
#include <queue>
#include <unordered_map>
#include <map>
#include <iomanip>
#include <complex>
#define int long long
using namespace std;
struct antenna {
int a, b, h;
antenna() {}
antenna(int a, int b, int h): a(a), b(b), h(h) {}
};
int n;
const int maxn = 2e5;
const int inf = 1e15;
vector<antenna> a;
int tree[maxn * 4];
int mn[maxn * 4];
int smn[maxn * 4];
int mnVal[maxn * 4];
int h[maxn];
void init() {
fill(tree, tree + maxn * 4, -inf * 2);
fill(mn, mn + maxn * 4, -inf);
fill(smn, smn + maxn * 4, inf);
fill(mnVal, mnVal + maxn * 4, inf);
fill(h, h + maxn, inf);
}
void tag(int i, int x) {
tree[i] = max(tree[i], x - mnVal[i]);
mn[i] = max(x, mn[i]);
}
void push(int i) {
tag(i * 2 + 1, mn[i]);
tag(i * 2 + 2, mn[i]);
}
void merge(int i, int l, int r) {
tree[i] = max({ tree[i], tree[l], tree[r] });
mn[i] = min(mn[l], mn[r]);
mnVal[i] = min(mnVal[l], mnVal[r]);
smn[i] = min(smn[l], smn[r]);
if (mn[l] != mn[r]) {
smn[i] = min(smn[i], max(mn[l], mn[r]));
}
}
void chmax(int i, int l, int r, int ql, int qr, int x) {
if (qr <= l || r <= ql || mn[i] >= x) {
return;
}
if (ql <= l && r <= qr && smn[i] > x) {
tag(i, x);
return;
}
int m = (l + r) / 2;
push(i);
chmax(i * 2 + 1, l, m, ql, qr, x);
chmax(i * 2 + 2, m, r, ql, qr, x);
merge(i, i * 2 + 1, i * 2 + 2);
}
void setinf(int i, int l, int r, int qi) {
if (qi < l || r <= qi) {
return;
}
if (l + 1 == r) {
mn[i] = -inf;
return;
}
int m = (l + r) / 2;
push(i);
setinf(i * 2 + 1, l, m, qi);
setinf(i * 2 + 2, m, r, qi);
merge(i, i * 2 + 1, i * 2 + 2);
}
void updval(int i, int l, int r, int qi, int x) {
if (qi < l || r <= qi) {
return;
}
if (l + 1 == r) {
tree[i] = max(tree[i], mn[i] - x);
mnVal[i] = x;
return;
}
int m = (l + r) / 2;
push(i);
updval(i * 2 + 1, l, m, qi, x);
updval(i * 2 + 2, m, r, qi, x);
merge(i, i * 2 + 1, i * 2 + 2);
}
void enable(int j) {
h[j] = a[j].h;
setinf(0, 0, n, j);
updval(0, 0, n, j, h[j]);
}
void disable(int j) {
h[j] = inf;
updval(0, 0, n, j, h[j]);
}
int get(int i, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) {
return -2;
}
if (ql <= l && r <= qr) {
return tree[i];
}
int m = (l + r) / 2;
push(i);
int res = max(get(i * 2 + 1, l, m, ql, qr), get(i * 2 + 2, m, r, ql, qr));
merge(i, i * 2 + 1, i * 2 + 2);
return res;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
a.resize(n);
for (int i = 0; i < n; ++i) {
int x, y, h;
cin >> h >> x >> y;
a[i] = antenna(x, y, h);
}
vector<vector<pair<int, int>>> queries(n + 1);
int q;
cin >> q;
vector<int> ans(q, -1);
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
queries[r - 1].push_back({ l - 1, i });
}
auto solve = [&] {
init();
vector<vector<int>> add(n + 1);
vector<vector<int>> del(n + 1);
for (int i = 0; i < n; ++i) {
add[min(i + a[i].a, n)].push_back(i);
del[min(i + a[i].b + 1, n)].push_back(i);
for (int j : add[i]) {
enable(j);
}
for (int j : del[i]) {
disable(j);
}
int L = max(0ll, i - a[i].b);
int R = max(0ll, i - a[i].a + 1);
chmax(0, 0, n, L, R, a[i].h);
for (auto [l, j] : queries[i]) {
ans[j] = max(ans[j], get(0, 0, n, l, i + 1));
}
}
};
solve();
for (int i = 0; i < n; ++i) {
a[i].h *= -1;
}
solve();
for (int i : ans) {
cout << i << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
26836 KB |
Output is correct |
2 |
Correct |
19 ms |
26984 KB |
Output is correct |
3 |
Correct |
15 ms |
26980 KB |
Output is correct |
4 |
Correct |
16 ms |
26972 KB |
Output is correct |
5 |
Correct |
16 ms |
26964 KB |
Output is correct |
6 |
Correct |
18 ms |
26920 KB |
Output is correct |
7 |
Correct |
16 ms |
26984 KB |
Output is correct |
8 |
Correct |
23 ms |
26964 KB |
Output is correct |
9 |
Correct |
17 ms |
26836 KB |
Output is correct |
10 |
Correct |
17 ms |
26888 KB |
Output is correct |
11 |
Correct |
17 ms |
26840 KB |
Output is correct |
12 |
Correct |
17 ms |
26928 KB |
Output is correct |
13 |
Correct |
18 ms |
26860 KB |
Output is correct |
14 |
Correct |
16 ms |
26964 KB |
Output is correct |
15 |
Correct |
16 ms |
26952 KB |
Output is correct |
16 |
Correct |
15 ms |
26980 KB |
Output is correct |
17 |
Correct |
15 ms |
26964 KB |
Output is correct |
18 |
Correct |
17 ms |
26980 KB |
Output is correct |
19 |
Correct |
20 ms |
26964 KB |
Output is correct |
20 |
Correct |
19 ms |
26864 KB |
Output is correct |
21 |
Correct |
15 ms |
26964 KB |
Output is correct |
22 |
Correct |
16 ms |
26964 KB |
Output is correct |
23 |
Correct |
15 ms |
26964 KB |
Output is correct |
24 |
Correct |
17 ms |
26924 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
26836 KB |
Output is correct |
2 |
Correct |
19 ms |
26984 KB |
Output is correct |
3 |
Correct |
15 ms |
26980 KB |
Output is correct |
4 |
Correct |
16 ms |
26972 KB |
Output is correct |
5 |
Correct |
16 ms |
26964 KB |
Output is correct |
6 |
Correct |
18 ms |
26920 KB |
Output is correct |
7 |
Correct |
16 ms |
26984 KB |
Output is correct |
8 |
Correct |
23 ms |
26964 KB |
Output is correct |
9 |
Correct |
17 ms |
26836 KB |
Output is correct |
10 |
Correct |
17 ms |
26888 KB |
Output is correct |
11 |
Correct |
17 ms |
26840 KB |
Output is correct |
12 |
Correct |
17 ms |
26928 KB |
Output is correct |
13 |
Correct |
18 ms |
26860 KB |
Output is correct |
14 |
Correct |
16 ms |
26964 KB |
Output is correct |
15 |
Correct |
16 ms |
26952 KB |
Output is correct |
16 |
Correct |
15 ms |
26980 KB |
Output is correct |
17 |
Correct |
15 ms |
26964 KB |
Output is correct |
18 |
Correct |
17 ms |
26980 KB |
Output is correct |
19 |
Correct |
20 ms |
26964 KB |
Output is correct |
20 |
Correct |
19 ms |
26864 KB |
Output is correct |
21 |
Correct |
15 ms |
26964 KB |
Output is correct |
22 |
Correct |
16 ms |
26964 KB |
Output is correct |
23 |
Correct |
15 ms |
26964 KB |
Output is correct |
24 |
Correct |
17 ms |
26924 KB |
Output is correct |
25 |
Correct |
139 ms |
32812 KB |
Output is correct |
26 |
Correct |
35 ms |
27724 KB |
Output is correct |
27 |
Correct |
217 ms |
35276 KB |
Output is correct |
28 |
Correct |
207 ms |
35260 KB |
Output is correct |
29 |
Correct |
171 ms |
33028 KB |
Output is correct |
30 |
Correct |
148 ms |
32732 KB |
Output is correct |
31 |
Correct |
151 ms |
34292 KB |
Output is correct |
32 |
Correct |
204 ms |
35268 KB |
Output is correct |
33 |
Correct |
208 ms |
34720 KB |
Output is correct |
34 |
Correct |
104 ms |
31036 KB |
Output is correct |
35 |
Correct |
201 ms |
35068 KB |
Output is correct |
36 |
Correct |
232 ms |
35308 KB |
Output is correct |
37 |
Correct |
115 ms |
31308 KB |
Output is correct |
38 |
Correct |
194 ms |
34424 KB |
Output is correct |
39 |
Correct |
52 ms |
28108 KB |
Output is correct |
40 |
Correct |
227 ms |
34328 KB |
Output is correct |
41 |
Correct |
144 ms |
32380 KB |
Output is correct |
42 |
Correct |
235 ms |
34388 KB |
Output is correct |
43 |
Correct |
79 ms |
29500 KB |
Output is correct |
44 |
Correct |
195 ms |
34340 KB |
Output is correct |
45 |
Correct |
54 ms |
28332 KB |
Output is correct |
46 |
Correct |
209 ms |
34400 KB |
Output is correct |
47 |
Correct |
63 ms |
28880 KB |
Output is correct |
48 |
Correct |
211 ms |
34324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
548 ms |
50984 KB |
Output is correct |
2 |
Correct |
568 ms |
57796 KB |
Output is correct |
3 |
Correct |
331 ms |
48416 KB |
Output is correct |
4 |
Correct |
627 ms |
57848 KB |
Output is correct |
5 |
Correct |
237 ms |
40908 KB |
Output is correct |
6 |
Correct |
560 ms |
57308 KB |
Output is correct |
7 |
Correct |
482 ms |
53060 KB |
Output is correct |
8 |
Correct |
539 ms |
57256 KB |
Output is correct |
9 |
Correct |
68 ms |
31672 KB |
Output is correct |
10 |
Correct |
557 ms |
57504 KB |
Output is correct |
11 |
Correct |
315 ms |
45588 KB |
Output is correct |
12 |
Correct |
603 ms |
57720 KB |
Output is correct |
13 |
Correct |
379 ms |
55308 KB |
Output is correct |
14 |
Correct |
339 ms |
56124 KB |
Output is correct |
15 |
Correct |
345 ms |
55496 KB |
Output is correct |
16 |
Correct |
312 ms |
55472 KB |
Output is correct |
17 |
Correct |
370 ms |
55528 KB |
Output is correct |
18 |
Correct |
339 ms |
55608 KB |
Output is correct |
19 |
Correct |
357 ms |
55484 KB |
Output is correct |
20 |
Correct |
325 ms |
55484 KB |
Output is correct |
21 |
Correct |
330 ms |
54900 KB |
Output is correct |
22 |
Correct |
312 ms |
56296 KB |
Output is correct |
23 |
Correct |
346 ms |
55232 KB |
Output is correct |
24 |
Correct |
299 ms |
55364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
26836 KB |
Output is correct |
2 |
Correct |
19 ms |
26984 KB |
Output is correct |
3 |
Correct |
15 ms |
26980 KB |
Output is correct |
4 |
Correct |
16 ms |
26972 KB |
Output is correct |
5 |
Correct |
16 ms |
26964 KB |
Output is correct |
6 |
Correct |
18 ms |
26920 KB |
Output is correct |
7 |
Correct |
16 ms |
26984 KB |
Output is correct |
8 |
Correct |
23 ms |
26964 KB |
Output is correct |
9 |
Correct |
17 ms |
26836 KB |
Output is correct |
10 |
Correct |
17 ms |
26888 KB |
Output is correct |
11 |
Correct |
17 ms |
26840 KB |
Output is correct |
12 |
Correct |
17 ms |
26928 KB |
Output is correct |
13 |
Correct |
18 ms |
26860 KB |
Output is correct |
14 |
Correct |
16 ms |
26964 KB |
Output is correct |
15 |
Correct |
16 ms |
26952 KB |
Output is correct |
16 |
Correct |
15 ms |
26980 KB |
Output is correct |
17 |
Correct |
15 ms |
26964 KB |
Output is correct |
18 |
Correct |
17 ms |
26980 KB |
Output is correct |
19 |
Correct |
20 ms |
26964 KB |
Output is correct |
20 |
Correct |
19 ms |
26864 KB |
Output is correct |
21 |
Correct |
15 ms |
26964 KB |
Output is correct |
22 |
Correct |
16 ms |
26964 KB |
Output is correct |
23 |
Correct |
15 ms |
26964 KB |
Output is correct |
24 |
Correct |
17 ms |
26924 KB |
Output is correct |
25 |
Correct |
139 ms |
32812 KB |
Output is correct |
26 |
Correct |
35 ms |
27724 KB |
Output is correct |
27 |
Correct |
217 ms |
35276 KB |
Output is correct |
28 |
Correct |
207 ms |
35260 KB |
Output is correct |
29 |
Correct |
171 ms |
33028 KB |
Output is correct |
30 |
Correct |
148 ms |
32732 KB |
Output is correct |
31 |
Correct |
151 ms |
34292 KB |
Output is correct |
32 |
Correct |
204 ms |
35268 KB |
Output is correct |
33 |
Correct |
208 ms |
34720 KB |
Output is correct |
34 |
Correct |
104 ms |
31036 KB |
Output is correct |
35 |
Correct |
201 ms |
35068 KB |
Output is correct |
36 |
Correct |
232 ms |
35308 KB |
Output is correct |
37 |
Correct |
115 ms |
31308 KB |
Output is correct |
38 |
Correct |
194 ms |
34424 KB |
Output is correct |
39 |
Correct |
52 ms |
28108 KB |
Output is correct |
40 |
Correct |
227 ms |
34328 KB |
Output is correct |
41 |
Correct |
144 ms |
32380 KB |
Output is correct |
42 |
Correct |
235 ms |
34388 KB |
Output is correct |
43 |
Correct |
79 ms |
29500 KB |
Output is correct |
44 |
Correct |
195 ms |
34340 KB |
Output is correct |
45 |
Correct |
54 ms |
28332 KB |
Output is correct |
46 |
Correct |
209 ms |
34400 KB |
Output is correct |
47 |
Correct |
63 ms |
28880 KB |
Output is correct |
48 |
Correct |
211 ms |
34324 KB |
Output is correct |
49 |
Correct |
548 ms |
50984 KB |
Output is correct |
50 |
Correct |
568 ms |
57796 KB |
Output is correct |
51 |
Correct |
331 ms |
48416 KB |
Output is correct |
52 |
Correct |
627 ms |
57848 KB |
Output is correct |
53 |
Correct |
237 ms |
40908 KB |
Output is correct |
54 |
Correct |
560 ms |
57308 KB |
Output is correct |
55 |
Correct |
482 ms |
53060 KB |
Output is correct |
56 |
Correct |
539 ms |
57256 KB |
Output is correct |
57 |
Correct |
68 ms |
31672 KB |
Output is correct |
58 |
Correct |
557 ms |
57504 KB |
Output is correct |
59 |
Correct |
315 ms |
45588 KB |
Output is correct |
60 |
Correct |
603 ms |
57720 KB |
Output is correct |
61 |
Correct |
379 ms |
55308 KB |
Output is correct |
62 |
Correct |
339 ms |
56124 KB |
Output is correct |
63 |
Correct |
345 ms |
55496 KB |
Output is correct |
64 |
Correct |
312 ms |
55472 KB |
Output is correct |
65 |
Correct |
370 ms |
55528 KB |
Output is correct |
66 |
Correct |
339 ms |
55608 KB |
Output is correct |
67 |
Correct |
357 ms |
55484 KB |
Output is correct |
68 |
Correct |
325 ms |
55484 KB |
Output is correct |
69 |
Correct |
330 ms |
54900 KB |
Output is correct |
70 |
Correct |
312 ms |
56296 KB |
Output is correct |
71 |
Correct |
346 ms |
55232 KB |
Output is correct |
72 |
Correct |
299 ms |
55364 KB |
Output is correct |
73 |
Correct |
802 ms |
63424 KB |
Output is correct |
74 |
Correct |
565 ms |
58596 KB |
Output is correct |
75 |
Correct |
795 ms |
59304 KB |
Output is correct |
76 |
Correct |
1154 ms |
69020 KB |
Output is correct |
77 |
Correct |
532 ms |
48824 KB |
Output is correct |
78 |
Correct |
864 ms |
64936 KB |
Output is correct |
79 |
Correct |
912 ms |
64112 KB |
Output is correct |
80 |
Correct |
995 ms |
68572 KB |
Output is correct |
81 |
Correct |
343 ms |
39916 KB |
Output is correct |
82 |
Correct |
785 ms |
62884 KB |
Output is correct |
83 |
Correct |
726 ms |
56560 KB |
Output is correct |
84 |
Correct |
967 ms |
68936 KB |
Output is correct |
85 |
Correct |
668 ms |
60828 KB |
Output is correct |
86 |
Correct |
732 ms |
65968 KB |
Output is correct |
87 |
Correct |
399 ms |
56900 KB |
Output is correct |
88 |
Correct |
746 ms |
65548 KB |
Output is correct |
89 |
Correct |
656 ms |
62920 KB |
Output is correct |
90 |
Correct |
757 ms |
65712 KB |
Output is correct |
91 |
Correct |
511 ms |
58784 KB |
Output is correct |
92 |
Correct |
756 ms |
64912 KB |
Output is correct |
93 |
Correct |
373 ms |
56780 KB |
Output is correct |
94 |
Correct |
745 ms |
66500 KB |
Output is correct |
95 |
Correct |
463 ms |
57996 KB |
Output is correct |
96 |
Correct |
725 ms |
65560 KB |
Output is correct |