#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
struct Node{
ll mx, mn, ans;
};
struct Tag{
ll mx, mn;
};
struct SegmentTree{
vector<Node> tree;
vector<Tag> lazy;
void init(ll n) {
ll sz = 1 << __lg(n-1) + 2;
tree.assign(sz, {-inf, inf, -1});
lazy.assign(sz, {-inf, inf});
}
Node Merge(Node u, Node v) {
return {max(u.mx, v.mx), min(u.mn, v.mn), max(u.ans, v.ans)};
}
void propagate(ll node, ll s, ll e) {
tree[node].ans = max({tree[node].ans, lazy[node].mx - tree[node].mn, tree[node].mx - lazy[node].mn});
if (s != e) {
for (auto &i : {node*2, node*2+1}) {
lazy[i].mx = max(lazy[i].mx, lazy[node].mx);
lazy[i].mn = min(lazy[i].mn, lazy[node].mn);
}
}
lazy[node] = {-inf, inf};
}
void update(ll node, ll s, ll e, ll l, ll r, ll val) {
propagate(node, s, e);
if (l > e || s > r) return;
if (l <= s && e <= r) {
lazy[node] = {val, val};
propagate(node, s, e);
return;
}
ll mid = s + e >> 1;
update(node*2, s, mid, l, r, val);
update(node*2+1, mid+1, e, l, r, val);
tree[node] = Merge(tree[node*2], tree[node*2+1]);
}
void modify(ll node, ll s, ll e, ll tar, ll val) {
propagate(node, s, e);
if (s > tar || tar > e) return;
if (s == e) {
if (val >= 0) {
tree[node].mx = val;
tree[node].mn = val;
}
else {
tree[node].mx = -inf;
tree[node].mn = inf;
}
return;
}
ll mid = s + e >> 1;
modify(node*2, s, mid, tar, val);
modify(node*2+1, mid+1, e, tar, val);
tree[node] = Merge(tree[node*2], tree[node*2+1]);
}
ll query(ll node, ll s, ll e, ll l, ll r) {
propagate(node, s, e);
if (l > e || s > r) return -1;
if (l <= s && e <= r) return tree[node].ans;
ll mid = s + e >> 1;
return max(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
}
};
SegmentTree seg;
ll h[200010], a[200010], b[200010];
ll l[200010], r[200010], ans[200010];
vector<ll> qrs[200010], add[200010], del[200010];
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
ll n;
cin >> n;
for (ll i=1; i<=n; i++) {
cin >> h[i] >> a[i] >> b[i];
if (i + a[i] <= n) add[i + a[i]].push_back(i);
if (i + b[i] <= n) del[i + b[i]].push_back(i);
}
ll q;
cin >> q;
for (ll i=1; i<=q; i++) {
cin >> l[i] >> r[i];
qrs[r[i]].push_back(i);
}
seg.init(n);
for (ll i=1; i<=n; i++) {
for (auto &j : add[i]) seg.modify(1, 1, n, j, h[j]);
seg.update(1, 1, n, i-b[i], i-a[i], h[i]);
for (auto &j : qrs[i]) ans[j] = seg.query(1, 1, n, l[j], r[j]);
for (auto &j : del[i]) seg.modify(1, 1, n, j, -1);
}
for (ll i=1; i<=q; i++) {
cout << ans[i] << '\n';
}
}
Compilation message
antennas.cpp: In member function 'void SegmentTree::init(ll)':
antennas.cpp:20:26: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
20 | ll sz = 1 << __lg(n-1) + 2;
| ~~~~~~~~~~^~~
antennas.cpp: In member function 'void SegmentTree::update(ll, ll, ll, ll, ll, ll)':
antennas.cpp:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | ll mid = s + e >> 1;
| ~~^~~
antennas.cpp: In member function 'void SegmentTree::modify(ll, ll, ll, ll, ll)':
antennas.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | ll mid = s + e >> 1;
| ~~^~~
antennas.cpp: In member function 'll SegmentTree::query(ll, ll, ll, ll, ll)':
antennas.cpp:73:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | ll mid = s + e >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
23128 KB |
Output is correct |
2 |
Correct |
6 ms |
23132 KB |
Output is correct |
3 |
Correct |
8 ms |
23388 KB |
Output is correct |
4 |
Correct |
6 ms |
23132 KB |
Output is correct |
5 |
Correct |
7 ms |
23188 KB |
Output is correct |
6 |
Correct |
6 ms |
23132 KB |
Output is correct |
7 |
Correct |
6 ms |
23132 KB |
Output is correct |
8 |
Correct |
6 ms |
23132 KB |
Output is correct |
9 |
Correct |
6 ms |
23132 KB |
Output is correct |
10 |
Correct |
6 ms |
23132 KB |
Output is correct |
11 |
Correct |
6 ms |
23132 KB |
Output is correct |
12 |
Correct |
6 ms |
23132 KB |
Output is correct |
13 |
Correct |
6 ms |
23132 KB |
Output is correct |
14 |
Correct |
7 ms |
23132 KB |
Output is correct |
15 |
Correct |
6 ms |
23132 KB |
Output is correct |
16 |
Correct |
8 ms |
23132 KB |
Output is correct |
17 |
Correct |
6 ms |
23132 KB |
Output is correct |
18 |
Correct |
6 ms |
23240 KB |
Output is correct |
19 |
Correct |
6 ms |
23192 KB |
Output is correct |
20 |
Correct |
7 ms |
23132 KB |
Output is correct |
21 |
Correct |
6 ms |
23132 KB |
Output is correct |
22 |
Correct |
7 ms |
23132 KB |
Output is correct |
23 |
Correct |
7 ms |
23132 KB |
Output is correct |
24 |
Correct |
7 ms |
23132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
23128 KB |
Output is correct |
2 |
Correct |
6 ms |
23132 KB |
Output is correct |
3 |
Correct |
8 ms |
23388 KB |
Output is correct |
4 |
Correct |
6 ms |
23132 KB |
Output is correct |
5 |
Correct |
7 ms |
23188 KB |
Output is correct |
6 |
Correct |
6 ms |
23132 KB |
Output is correct |
7 |
Correct |
6 ms |
23132 KB |
Output is correct |
8 |
Correct |
6 ms |
23132 KB |
Output is correct |
9 |
Correct |
6 ms |
23132 KB |
Output is correct |
10 |
Correct |
6 ms |
23132 KB |
Output is correct |
11 |
Correct |
6 ms |
23132 KB |
Output is correct |
12 |
Correct |
6 ms |
23132 KB |
Output is correct |
13 |
Correct |
6 ms |
23132 KB |
Output is correct |
14 |
Correct |
7 ms |
23132 KB |
Output is correct |
15 |
Correct |
6 ms |
23132 KB |
Output is correct |
16 |
Correct |
8 ms |
23132 KB |
Output is correct |
17 |
Correct |
6 ms |
23132 KB |
Output is correct |
18 |
Correct |
6 ms |
23240 KB |
Output is correct |
19 |
Correct |
6 ms |
23192 KB |
Output is correct |
20 |
Correct |
7 ms |
23132 KB |
Output is correct |
21 |
Correct |
6 ms |
23132 KB |
Output is correct |
22 |
Correct |
7 ms |
23132 KB |
Output is correct |
23 |
Correct |
7 ms |
23132 KB |
Output is correct |
24 |
Correct |
7 ms |
23132 KB |
Output is correct |
25 |
Correct |
64 ms |
27360 KB |
Output is correct |
26 |
Correct |
14 ms |
23768 KB |
Output is correct |
27 |
Correct |
91 ms |
29268 KB |
Output is correct |
28 |
Correct |
96 ms |
29424 KB |
Output is correct |
29 |
Correct |
71 ms |
27308 KB |
Output is correct |
30 |
Correct |
65 ms |
27220 KB |
Output is correct |
31 |
Correct |
71 ms |
28240 KB |
Output is correct |
32 |
Correct |
94 ms |
29280 KB |
Output is correct |
33 |
Correct |
84 ms |
29024 KB |
Output is correct |
34 |
Correct |
49 ms |
26196 KB |
Output is correct |
35 |
Correct |
91 ms |
29268 KB |
Output is correct |
36 |
Correct |
94 ms |
29284 KB |
Output is correct |
37 |
Correct |
57 ms |
26164 KB |
Output is correct |
38 |
Correct |
93 ms |
28496 KB |
Output is correct |
39 |
Correct |
21 ms |
23900 KB |
Output is correct |
40 |
Correct |
104 ms |
28328 KB |
Output is correct |
41 |
Correct |
78 ms |
27264 KB |
Output is correct |
42 |
Correct |
93 ms |
28244 KB |
Output is correct |
43 |
Correct |
36 ms |
24916 KB |
Output is correct |
44 |
Correct |
94 ms |
28304 KB |
Output is correct |
45 |
Correct |
22 ms |
24168 KB |
Output is correct |
46 |
Correct |
92 ms |
28500 KB |
Output is correct |
47 |
Correct |
31 ms |
24496 KB |
Output is correct |
48 |
Correct |
110 ms |
28524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
279 ms |
47444 KB |
Output is correct |
2 |
Correct |
293 ms |
52820 KB |
Output is correct |
3 |
Correct |
167 ms |
49528 KB |
Output is correct |
4 |
Correct |
281 ms |
52652 KB |
Output is correct |
5 |
Correct |
108 ms |
37112 KB |
Output is correct |
6 |
Correct |
293 ms |
52452 KB |
Output is correct |
7 |
Correct |
220 ms |
51284 KB |
Output is correct |
8 |
Correct |
261 ms |
52820 KB |
Output is correct |
9 |
Correct |
31 ms |
26972 KB |
Output is correct |
10 |
Correct |
297 ms |
52584 KB |
Output is correct |
11 |
Correct |
138 ms |
38476 KB |
Output is correct |
12 |
Correct |
262 ms |
52648 KB |
Output is correct |
13 |
Correct |
189 ms |
50644 KB |
Output is correct |
14 |
Correct |
177 ms |
51044 KB |
Output is correct |
15 |
Correct |
164 ms |
50764 KB |
Output is correct |
16 |
Correct |
145 ms |
51516 KB |
Output is correct |
17 |
Correct |
180 ms |
50992 KB |
Output is correct |
18 |
Correct |
166 ms |
51540 KB |
Output is correct |
19 |
Correct |
170 ms |
50756 KB |
Output is correct |
20 |
Correct |
173 ms |
51012 KB |
Output is correct |
21 |
Correct |
193 ms |
50752 KB |
Output is correct |
22 |
Correct |
188 ms |
51012 KB |
Output is correct |
23 |
Correct |
172 ms |
50708 KB |
Output is correct |
24 |
Correct |
146 ms |
50748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
23128 KB |
Output is correct |
2 |
Correct |
6 ms |
23132 KB |
Output is correct |
3 |
Correct |
8 ms |
23388 KB |
Output is correct |
4 |
Correct |
6 ms |
23132 KB |
Output is correct |
5 |
Correct |
7 ms |
23188 KB |
Output is correct |
6 |
Correct |
6 ms |
23132 KB |
Output is correct |
7 |
Correct |
6 ms |
23132 KB |
Output is correct |
8 |
Correct |
6 ms |
23132 KB |
Output is correct |
9 |
Correct |
6 ms |
23132 KB |
Output is correct |
10 |
Correct |
6 ms |
23132 KB |
Output is correct |
11 |
Correct |
6 ms |
23132 KB |
Output is correct |
12 |
Correct |
6 ms |
23132 KB |
Output is correct |
13 |
Correct |
6 ms |
23132 KB |
Output is correct |
14 |
Correct |
7 ms |
23132 KB |
Output is correct |
15 |
Correct |
6 ms |
23132 KB |
Output is correct |
16 |
Correct |
8 ms |
23132 KB |
Output is correct |
17 |
Correct |
6 ms |
23132 KB |
Output is correct |
18 |
Correct |
6 ms |
23240 KB |
Output is correct |
19 |
Correct |
6 ms |
23192 KB |
Output is correct |
20 |
Correct |
7 ms |
23132 KB |
Output is correct |
21 |
Correct |
6 ms |
23132 KB |
Output is correct |
22 |
Correct |
7 ms |
23132 KB |
Output is correct |
23 |
Correct |
7 ms |
23132 KB |
Output is correct |
24 |
Correct |
7 ms |
23132 KB |
Output is correct |
25 |
Correct |
64 ms |
27360 KB |
Output is correct |
26 |
Correct |
14 ms |
23768 KB |
Output is correct |
27 |
Correct |
91 ms |
29268 KB |
Output is correct |
28 |
Correct |
96 ms |
29424 KB |
Output is correct |
29 |
Correct |
71 ms |
27308 KB |
Output is correct |
30 |
Correct |
65 ms |
27220 KB |
Output is correct |
31 |
Correct |
71 ms |
28240 KB |
Output is correct |
32 |
Correct |
94 ms |
29280 KB |
Output is correct |
33 |
Correct |
84 ms |
29024 KB |
Output is correct |
34 |
Correct |
49 ms |
26196 KB |
Output is correct |
35 |
Correct |
91 ms |
29268 KB |
Output is correct |
36 |
Correct |
94 ms |
29284 KB |
Output is correct |
37 |
Correct |
57 ms |
26164 KB |
Output is correct |
38 |
Correct |
93 ms |
28496 KB |
Output is correct |
39 |
Correct |
21 ms |
23900 KB |
Output is correct |
40 |
Correct |
104 ms |
28328 KB |
Output is correct |
41 |
Correct |
78 ms |
27264 KB |
Output is correct |
42 |
Correct |
93 ms |
28244 KB |
Output is correct |
43 |
Correct |
36 ms |
24916 KB |
Output is correct |
44 |
Correct |
94 ms |
28304 KB |
Output is correct |
45 |
Correct |
22 ms |
24168 KB |
Output is correct |
46 |
Correct |
92 ms |
28500 KB |
Output is correct |
47 |
Correct |
31 ms |
24496 KB |
Output is correct |
48 |
Correct |
110 ms |
28524 KB |
Output is correct |
49 |
Correct |
279 ms |
47444 KB |
Output is correct |
50 |
Correct |
293 ms |
52820 KB |
Output is correct |
51 |
Correct |
167 ms |
49528 KB |
Output is correct |
52 |
Correct |
281 ms |
52652 KB |
Output is correct |
53 |
Correct |
108 ms |
37112 KB |
Output is correct |
54 |
Correct |
293 ms |
52452 KB |
Output is correct |
55 |
Correct |
220 ms |
51284 KB |
Output is correct |
56 |
Correct |
261 ms |
52820 KB |
Output is correct |
57 |
Correct |
31 ms |
26972 KB |
Output is correct |
58 |
Correct |
297 ms |
52584 KB |
Output is correct |
59 |
Correct |
138 ms |
38476 KB |
Output is correct |
60 |
Correct |
262 ms |
52648 KB |
Output is correct |
61 |
Correct |
189 ms |
50644 KB |
Output is correct |
62 |
Correct |
177 ms |
51044 KB |
Output is correct |
63 |
Correct |
164 ms |
50764 KB |
Output is correct |
64 |
Correct |
145 ms |
51516 KB |
Output is correct |
65 |
Correct |
180 ms |
50992 KB |
Output is correct |
66 |
Correct |
166 ms |
51540 KB |
Output is correct |
67 |
Correct |
170 ms |
50756 KB |
Output is correct |
68 |
Correct |
173 ms |
51012 KB |
Output is correct |
69 |
Correct |
193 ms |
50752 KB |
Output is correct |
70 |
Correct |
188 ms |
51012 KB |
Output is correct |
71 |
Correct |
172 ms |
50708 KB |
Output is correct |
72 |
Correct |
146 ms |
50748 KB |
Output is correct |
73 |
Correct |
486 ms |
57796 KB |
Output is correct |
74 |
Correct |
317 ms |
53372 KB |
Output is correct |
75 |
Correct |
456 ms |
57408 KB |
Output is correct |
76 |
Correct |
510 ms |
60976 KB |
Output is correct |
77 |
Correct |
247 ms |
42580 KB |
Output is correct |
78 |
Correct |
447 ms |
58452 KB |
Output is correct |
79 |
Correct |
470 ms |
59352 KB |
Output is correct |
80 |
Correct |
532 ms |
60864 KB |
Output is correct |
81 |
Correct |
191 ms |
33644 KB |
Output is correct |
82 |
Correct |
418 ms |
56916 KB |
Output is correct |
83 |
Correct |
348 ms |
46420 KB |
Output is correct |
84 |
Correct |
563 ms |
61008 KB |
Output is correct |
85 |
Correct |
339 ms |
55252 KB |
Output is correct |
86 |
Correct |
424 ms |
57936 KB |
Output is correct |
87 |
Correct |
212 ms |
52044 KB |
Output is correct |
88 |
Correct |
397 ms |
58536 KB |
Output is correct |
89 |
Correct |
370 ms |
56428 KB |
Output is correct |
90 |
Correct |
446 ms |
58684 KB |
Output is correct |
91 |
Correct |
273 ms |
53704 KB |
Output is correct |
92 |
Correct |
444 ms |
57868 KB |
Output is correct |
93 |
Correct |
238 ms |
52156 KB |
Output is correct |
94 |
Correct |
414 ms |
58148 KB |
Output is correct |
95 |
Correct |
262 ms |
52940 KB |
Output is correct |
96 |
Correct |
423 ms |
58060 KB |
Output is correct |