#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] = {val, val, -1};
else
tree[node] = {-inf, inf, -1};
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:60:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | ll mid = s + e >> 1;
| ~~^~~
antennas.cpp: In member function 'll SegmentTree::query(ll, ll, ll, ll, ll)':
antennas.cpp:69:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | ll mid = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
23128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
23128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
266 ms |
47584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
23128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
