#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 10;
struct Node{
int mx, mn, ans;
};
struct Tag{
int mx, mn;
};
struct SegmentTree{
vector<Node> tree;
vector<Tag> lazy;
void init(int n) {
int 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(int node, int s, int 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(int node, int s, int e, int l, int r, int 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;
}
int 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(int node, int s, int e, int tar, int 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;
}
int 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]);
}
int query(int node, int s, int e, int l, int r) {
propagate(node, s, e);
if (l > e || s > r) return -1;
if (l <= s && e <= r) return tree[node].ans;
int mid = s + e >> 1;
return max(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
}
};
SegmentTree seg;
int h[200010], a[200010], b[200010];
int l[200010], r[200010], ans[200010];
vector<int> qrs[200010], add[200010], del[200010];
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
int n;
cin >> n;
for (int 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);
}
int q;
cin >> q;
for (int i=1; i<=q; i++) {
cin >> l[i] >> r[i];
qrs[r[i]].push_back(i);
}
seg.init(n);
for (int 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 (int i=1; i<=q; i++) {
cout << ans[i] << '\n';
}
}
Compilation message
antennas.cpp: In member function 'void SegmentTree::init(int)':
antennas.cpp:19:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
19 | int sz = 1 << __lg(n-1) + 2;
| ~~~~~~~~~~^~~
antennas.cpp: In member function 'void SegmentTree::update(int, int, int, int, int, int)':
antennas.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | int mid = s + e >> 1;
| ~~^~~
antennas.cpp: In member function 'void SegmentTree::modify(int, int, int, int, int)':
antennas.cpp:59:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | int mid = s + e >> 1;
| ~~^~~
antennas.cpp: In member function 'int SegmentTree::query(int, int, int, int, int)':
antennas.cpp:68:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int mid = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
19288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
19288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
246 ms |
32620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
19288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
