#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define MAX 200100
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
struct node {
ll mxval, mnval;
ll ans;
node() {
mxval = mnval = ans = -1;
}
};
node operator+(const node& n1, const node& n2) {
node ret;
ret.mnval = n1.mnval == -1 ? n2.mnval : (n2.mnval == -1 ? n1.mnval : min(n1.mnval, n2.mnval));
ret.mxval = max(n1.mxval, n2.mxval);
ret.ans = max(n1.ans, n2.ans);
return ret;
}
struct segtree {
ll N, s;
vector<node> tree;
vector<ll> l, r;
vector<ll> lmx, lmn; //lazy max min
void init(ll x = 1) {
if (x >= s) {
l[x] = r[x] = x - s + 1;
return;
}
init(x * 2);
init(x * 2 + 1);
l[x] = l[x * 2];
r[x] = r[x * 2 + 1];
}
segtree() {}
segtree(ll N) {
segtree::N = N;
s = 1LL << (ll)ceil(log2(N));
tree.resize(2 * s + 1);
l.resize(2 * s + 1);
r.resize(2 * s + 1);
lmx.resize(2 * s + 1, -1);
lmn.resize(2 * s + 1, -1);
init();
}
void prop(ll loc) {
if (loc >= s) {
lmx[loc] = lmn[loc] = -1;
return;
}
lmx[loc * 2] = max(lmx[loc * 2], lmx[loc]);
lmx[loc * 2 + 1] = max(lmx[loc * 2 + 1], lmx[loc]);
if (lmx[loc] != -1) lmn[loc * 2] = min(lmn[loc * 2], lmn[loc]);
if (lmx[loc] != -1) lmn[loc * 2 + 1] = min(lmn[loc * 2 + 1], lmn[loc]);
if (lmn[loc * 2] == -1) lmn[loc * 2] = lmn[loc];
if (lmn[loc * 2 + 1] == -1) lmn[loc * 2 + 1] = lmn[loc];
ll res = -1;
if (tree[loc * 2].mxval != -1 && lmx[loc * 2] != -1) res = max(res, abs(tree[loc * 2].mxval - lmx[loc * 2]));
if (tree[loc * 2].mxval != -1 && lmn[loc * 2] != -1) res = max(res, abs(tree[loc * 2].mxval - lmn[loc * 2]));
if (tree[loc * 2].mnval != -1 && lmx[loc * 2] != -1) res = max(res, abs(tree[loc * 2].mnval - lmx[loc * 2]));
if (tree[loc * 2].mnval != -1 && lmn[loc * 2] != -1) res = max(res, abs(tree[loc * 2].mnval - lmn[loc * 2]));
tree[loc * 2].ans = max(tree[loc * 2].ans, res);
res = -1;
if (tree[loc * 2 + 1].mxval != -1 && lmx[loc * 2 + 1] != -1) res = max(res, abs(tree[loc * 2 + 1].mxval - lmx[loc * 2 + 1]));
if (tree[loc * 2 + 1].mxval != -1 && lmn[loc * 2 + 1] != -1) res = max(res, abs(tree[loc * 2 + 1].mxval - lmn[loc * 2 + 1]));
if (tree[loc * 2 + 1].mnval != -1 && lmx[loc * 2 + 1] != -1) res = max(res, abs(tree[loc * 2 + 1].mnval - lmx[loc * 2 + 1]));
if (tree[loc * 2 + 1].mnval != -1 && lmn[loc * 2 + 1] != -1) res = max(res, abs(tree[loc * 2 + 1].mnval - lmn[loc * 2 + 1]));
tree[loc * 2 + 1].ans = max(tree[loc * 2 + 1].ans, res);
lmx[loc] = lmn[loc] = -1;
}
void update(ll low, ll high, ll h, ll loc = 1) {
prop(loc);
if (high == 0) return;
low = max(1LL, low);
if (tree[loc].mnval == -1) return;
prop(loc);
if (low == l[loc] && high == r[loc]) {
lmx[loc] = max(lmx[loc], h);
lmn[loc] = min(lmn[loc], h);
if (lmn[loc] == -1) lmn[loc] = h;
ll res = 0;
if (tree[loc].mnval != -1) res = max(res, abs(h - tree[loc].mnval));
if (tree[loc].mxval != -1) res = max(res, abs(h - tree[loc].mxval));
tree[loc].ans = max(tree[loc].ans, res);
return;
}
if (high <= r[loc * 2]) update(low, high, h, loc * 2);
else if (low >= l[loc * 2 + 1]) update(low, high, h, loc * 2 + 1);
else update(low, r[loc * 2], h, loc * 2), update(l[loc * 2 + 1], high, h, loc * 2 + 1);
tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
}
void togle(ll x, ll v, ll loc = 1) {
prop(loc);
if (l[loc] == r[loc]) {
tree[loc].mnval = tree[loc].mxval = v;
return;
}
if (x <= r[loc * 2]) togle(x, v, loc * 2);
else togle(x, v, loc * 2 + 1);
tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
}
ll query(ll low, ll high, ll loc = 1) {
prop(loc);
if (low == l[loc] && high == r[loc]) return tree[loc].ans;
if (high <= r[loc * 2]) return query(low, high, loc * 2);
if (low >= l[loc * 2 + 1]) return query(low, high, loc * 2 + 1);
return max(query(low, r[loc * 2], loc * 2), query(l[loc * 2 + 1], high, loc * 2 + 1));
}
};
struct query {
ll l, r;
ll ind;
query() {}
query(ll l, ll r, ll ind) :l(l), r(r), ind(ind) {}
};
vector<query> qarr[MAX];
vector<ll> on[MAX], off[MAX];
ll ans[MAX];
ll H[MAX];
ll l[MAX], r[MAX];
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
ll N;
cin >> N;
ll i;
ll a, b;
for (i = 1; i <= N; i++) {
cin >> H[i] >> a >> b;
l[i] = max(i - b, 0LL);
r[i] = max(i - a, 0LL);
on[min(N + 1, i + a)].push_back(i);
off[min(N + 1, i + b + 1)].push_back(i);
}
ll Q;
cin >> Q;
for (i = 1; i <= Q; i++) {
cin >> a >> b;
qarr[b].push_back(query(a, b, i));
}
segtree seg(N);
for (i = 1; i <= N; i++) {
for (auto x : on[i]) seg.togle(x, H[x]);
for (auto x : off[i]) seg.togle(x, -1);
seg.update(l[i], r[i], H[i]);
for (auto q : qarr[i]) ans[q.ind] = seg.query(q.l, i);
}
for (i = 1; i <= Q; i++) cout << ans[i] << ln;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14412 KB |
Output is correct |
2 |
Correct |
8 ms |
14416 KB |
Output is correct |
3 |
Correct |
9 ms |
14412 KB |
Output is correct |
4 |
Correct |
8 ms |
14412 KB |
Output is correct |
5 |
Correct |
9 ms |
14552 KB |
Output is correct |
6 |
Correct |
8 ms |
14424 KB |
Output is correct |
7 |
Correct |
9 ms |
14412 KB |
Output is correct |
8 |
Correct |
8 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14412 KB |
Output is correct |
10 |
Correct |
8 ms |
14412 KB |
Output is correct |
11 |
Correct |
8 ms |
14412 KB |
Output is correct |
12 |
Correct |
10 ms |
14412 KB |
Output is correct |
13 |
Correct |
9 ms |
14456 KB |
Output is correct |
14 |
Correct |
9 ms |
14412 KB |
Output is correct |
15 |
Correct |
8 ms |
14396 KB |
Output is correct |
16 |
Correct |
8 ms |
14412 KB |
Output is correct |
17 |
Correct |
9 ms |
14412 KB |
Output is correct |
18 |
Correct |
8 ms |
14424 KB |
Output is correct |
19 |
Correct |
8 ms |
14412 KB |
Output is correct |
20 |
Correct |
10 ms |
14384 KB |
Output is correct |
21 |
Correct |
10 ms |
14412 KB |
Output is correct |
22 |
Correct |
9 ms |
14424 KB |
Output is correct |
23 |
Correct |
9 ms |
14412 KB |
Output is correct |
24 |
Correct |
8 ms |
14412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14412 KB |
Output is correct |
2 |
Correct |
8 ms |
14416 KB |
Output is correct |
3 |
Correct |
9 ms |
14412 KB |
Output is correct |
4 |
Correct |
8 ms |
14412 KB |
Output is correct |
5 |
Correct |
9 ms |
14552 KB |
Output is correct |
6 |
Correct |
8 ms |
14424 KB |
Output is correct |
7 |
Correct |
9 ms |
14412 KB |
Output is correct |
8 |
Correct |
8 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14412 KB |
Output is correct |
10 |
Correct |
8 ms |
14412 KB |
Output is correct |
11 |
Correct |
8 ms |
14412 KB |
Output is correct |
12 |
Correct |
10 ms |
14412 KB |
Output is correct |
13 |
Correct |
9 ms |
14456 KB |
Output is correct |
14 |
Correct |
9 ms |
14412 KB |
Output is correct |
15 |
Correct |
8 ms |
14396 KB |
Output is correct |
16 |
Correct |
8 ms |
14412 KB |
Output is correct |
17 |
Correct |
9 ms |
14412 KB |
Output is correct |
18 |
Correct |
8 ms |
14424 KB |
Output is correct |
19 |
Correct |
8 ms |
14412 KB |
Output is correct |
20 |
Correct |
10 ms |
14384 KB |
Output is correct |
21 |
Correct |
10 ms |
14412 KB |
Output is correct |
22 |
Correct |
9 ms |
14424 KB |
Output is correct |
23 |
Correct |
9 ms |
14412 KB |
Output is correct |
24 |
Correct |
8 ms |
14412 KB |
Output is correct |
25 |
Correct |
126 ms |
23108 KB |
Output is correct |
26 |
Correct |
25 ms |
15700 KB |
Output is correct |
27 |
Correct |
177 ms |
26828 KB |
Output is correct |
28 |
Correct |
190 ms |
26968 KB |
Output is correct |
29 |
Correct |
114 ms |
23344 KB |
Output is correct |
30 |
Correct |
122 ms |
22980 KB |
Output is correct |
31 |
Correct |
131 ms |
25204 KB |
Output is correct |
32 |
Correct |
179 ms |
26940 KB |
Output is correct |
33 |
Correct |
173 ms |
26016 KB |
Output is correct |
34 |
Correct |
96 ms |
20676 KB |
Output is correct |
35 |
Correct |
170 ms |
26624 KB |
Output is correct |
36 |
Correct |
186 ms |
27024 KB |
Output is correct |
37 |
Correct |
92 ms |
21308 KB |
Output is correct |
38 |
Correct |
159 ms |
25964 KB |
Output is correct |
39 |
Correct |
30 ms |
16224 KB |
Output is correct |
40 |
Correct |
156 ms |
25976 KB |
Output is correct |
41 |
Correct |
119 ms |
22952 KB |
Output is correct |
42 |
Correct |
163 ms |
25904 KB |
Output is correct |
43 |
Correct |
58 ms |
18500 KB |
Output is correct |
44 |
Correct |
159 ms |
25900 KB |
Output is correct |
45 |
Correct |
35 ms |
16576 KB |
Output is correct |
46 |
Correct |
159 ms |
25924 KB |
Output is correct |
47 |
Correct |
50 ms |
17608 KB |
Output is correct |
48 |
Correct |
164 ms |
26004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
620 ms |
54468 KB |
Output is correct |
2 |
Correct |
689 ms |
55448 KB |
Output is correct |
3 |
Correct |
447 ms |
52144 KB |
Output is correct |
4 |
Correct |
658 ms |
55452 KB |
Output is correct |
5 |
Correct |
280 ms |
35764 KB |
Output is correct |
6 |
Correct |
670 ms |
57480 KB |
Output is correct |
7 |
Correct |
564 ms |
55692 KB |
Output is correct |
8 |
Correct |
662 ms |
57500 KB |
Output is correct |
9 |
Correct |
81 ms |
20424 KB |
Output is correct |
10 |
Correct |
661 ms |
58468 KB |
Output is correct |
11 |
Correct |
389 ms |
38192 KB |
Output is correct |
12 |
Correct |
722 ms |
58448 KB |
Output is correct |
13 |
Correct |
347 ms |
56292 KB |
Output is correct |
14 |
Correct |
319 ms |
56128 KB |
Output is correct |
15 |
Correct |
325 ms |
56044 KB |
Output is correct |
16 |
Correct |
290 ms |
56360 KB |
Output is correct |
17 |
Correct |
376 ms |
56128 KB |
Output is correct |
18 |
Correct |
373 ms |
56252 KB |
Output is correct |
19 |
Correct |
374 ms |
56112 KB |
Output is correct |
20 |
Correct |
357 ms |
55992 KB |
Output is correct |
21 |
Correct |
314 ms |
56700 KB |
Output is correct |
22 |
Correct |
354 ms |
56080 KB |
Output is correct |
23 |
Correct |
385 ms |
56396 KB |
Output is correct |
24 |
Correct |
344 ms |
56708 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14412 KB |
Output is correct |
2 |
Correct |
8 ms |
14416 KB |
Output is correct |
3 |
Correct |
9 ms |
14412 KB |
Output is correct |
4 |
Correct |
8 ms |
14412 KB |
Output is correct |
5 |
Correct |
9 ms |
14552 KB |
Output is correct |
6 |
Correct |
8 ms |
14424 KB |
Output is correct |
7 |
Correct |
9 ms |
14412 KB |
Output is correct |
8 |
Correct |
8 ms |
14420 KB |
Output is correct |
9 |
Correct |
8 ms |
14412 KB |
Output is correct |
10 |
Correct |
8 ms |
14412 KB |
Output is correct |
11 |
Correct |
8 ms |
14412 KB |
Output is correct |
12 |
Correct |
10 ms |
14412 KB |
Output is correct |
13 |
Correct |
9 ms |
14456 KB |
Output is correct |
14 |
Correct |
9 ms |
14412 KB |
Output is correct |
15 |
Correct |
8 ms |
14396 KB |
Output is correct |
16 |
Correct |
8 ms |
14412 KB |
Output is correct |
17 |
Correct |
9 ms |
14412 KB |
Output is correct |
18 |
Correct |
8 ms |
14424 KB |
Output is correct |
19 |
Correct |
8 ms |
14412 KB |
Output is correct |
20 |
Correct |
10 ms |
14384 KB |
Output is correct |
21 |
Correct |
10 ms |
14412 KB |
Output is correct |
22 |
Correct |
9 ms |
14424 KB |
Output is correct |
23 |
Correct |
9 ms |
14412 KB |
Output is correct |
24 |
Correct |
8 ms |
14412 KB |
Output is correct |
25 |
Correct |
126 ms |
23108 KB |
Output is correct |
26 |
Correct |
25 ms |
15700 KB |
Output is correct |
27 |
Correct |
177 ms |
26828 KB |
Output is correct |
28 |
Correct |
190 ms |
26968 KB |
Output is correct |
29 |
Correct |
114 ms |
23344 KB |
Output is correct |
30 |
Correct |
122 ms |
22980 KB |
Output is correct |
31 |
Correct |
131 ms |
25204 KB |
Output is correct |
32 |
Correct |
179 ms |
26940 KB |
Output is correct |
33 |
Correct |
173 ms |
26016 KB |
Output is correct |
34 |
Correct |
96 ms |
20676 KB |
Output is correct |
35 |
Correct |
170 ms |
26624 KB |
Output is correct |
36 |
Correct |
186 ms |
27024 KB |
Output is correct |
37 |
Correct |
92 ms |
21308 KB |
Output is correct |
38 |
Correct |
159 ms |
25964 KB |
Output is correct |
39 |
Correct |
30 ms |
16224 KB |
Output is correct |
40 |
Correct |
156 ms |
25976 KB |
Output is correct |
41 |
Correct |
119 ms |
22952 KB |
Output is correct |
42 |
Correct |
163 ms |
25904 KB |
Output is correct |
43 |
Correct |
58 ms |
18500 KB |
Output is correct |
44 |
Correct |
159 ms |
25900 KB |
Output is correct |
45 |
Correct |
35 ms |
16576 KB |
Output is correct |
46 |
Correct |
159 ms |
25924 KB |
Output is correct |
47 |
Correct |
50 ms |
17608 KB |
Output is correct |
48 |
Correct |
164 ms |
26004 KB |
Output is correct |
49 |
Correct |
620 ms |
54468 KB |
Output is correct |
50 |
Correct |
689 ms |
55448 KB |
Output is correct |
51 |
Correct |
447 ms |
52144 KB |
Output is correct |
52 |
Correct |
658 ms |
55452 KB |
Output is correct |
53 |
Correct |
280 ms |
35764 KB |
Output is correct |
54 |
Correct |
670 ms |
57480 KB |
Output is correct |
55 |
Correct |
564 ms |
55692 KB |
Output is correct |
56 |
Correct |
662 ms |
57500 KB |
Output is correct |
57 |
Correct |
81 ms |
20424 KB |
Output is correct |
58 |
Correct |
661 ms |
58468 KB |
Output is correct |
59 |
Correct |
389 ms |
38192 KB |
Output is correct |
60 |
Correct |
722 ms |
58448 KB |
Output is correct |
61 |
Correct |
347 ms |
56292 KB |
Output is correct |
62 |
Correct |
319 ms |
56128 KB |
Output is correct |
63 |
Correct |
325 ms |
56044 KB |
Output is correct |
64 |
Correct |
290 ms |
56360 KB |
Output is correct |
65 |
Correct |
376 ms |
56128 KB |
Output is correct |
66 |
Correct |
373 ms |
56252 KB |
Output is correct |
67 |
Correct |
374 ms |
56112 KB |
Output is correct |
68 |
Correct |
357 ms |
55992 KB |
Output is correct |
69 |
Correct |
314 ms |
56700 KB |
Output is correct |
70 |
Correct |
354 ms |
56080 KB |
Output is correct |
71 |
Correct |
385 ms |
56396 KB |
Output is correct |
72 |
Correct |
344 ms |
56708 KB |
Output is correct |
73 |
Correct |
1047 ms |
65868 KB |
Output is correct |
74 |
Correct |
760 ms |
59008 KB |
Output is correct |
75 |
Correct |
977 ms |
66148 KB |
Output is correct |
76 |
Correct |
1244 ms |
70624 KB |
Output is correct |
77 |
Correct |
618 ms |
44852 KB |
Output is correct |
78 |
Correct |
1062 ms |
66324 KB |
Output is correct |
79 |
Correct |
1147 ms |
68636 KB |
Output is correct |
80 |
Correct |
1357 ms |
70652 KB |
Output is correct |
81 |
Correct |
415 ms |
32704 KB |
Output is correct |
82 |
Correct |
947 ms |
64048 KB |
Output is correct |
83 |
Correct |
945 ms |
50628 KB |
Output is correct |
84 |
Correct |
1316 ms |
70620 KB |
Output is correct |
85 |
Correct |
608 ms |
62236 KB |
Output is correct |
86 |
Correct |
732 ms |
67440 KB |
Output is correct |
87 |
Correct |
375 ms |
57380 KB |
Output is correct |
88 |
Correct |
661 ms |
67792 KB |
Output is correct |
89 |
Correct |
652 ms |
64120 KB |
Output is correct |
90 |
Correct |
679 ms |
67912 KB |
Output is correct |
91 |
Correct |
546 ms |
59376 KB |
Output is correct |
92 |
Correct |
713 ms |
67276 KB |
Output is correct |
93 |
Correct |
416 ms |
57480 KB |
Output is correct |
94 |
Correct |
787 ms |
67412 KB |
Output is correct |
95 |
Correct |
446 ms |
58676 KB |
Output is correct |
96 |
Correct |
664 ms |
67384 KB |
Output is correct |