#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
struct segment_tree {
int n;
vector<ll> tree, mn, lazy;
segment_tree(int _n) : n(_n), tree(4*n, -inf), lazy(4*n, -inf), mn(4*n, inf) {}
void pull(int u, ll x) {
tree[u] = max(tree[u], x - mn[u]);
lazy[u] = max(lazy[u], x);
}
void push(int u, int tl, int tr) {
if(lazy[u] == -inf) return ;
if(tl != tr) {
pull(2*u, lazy[u]);
pull(2*u+1, lazy[u]);
}
lazy[u] = -inf;
}
void set_mn(int u, int tl, int tr, int p, ll v) {
if(tl == tr) {
mn[u] = v;
} else {
push(u, tl, tr);
int tm = (tl + tr) / 2;
if(p <= tm) set_mn(2*u, tl, tm, p, v);
else set_mn(2*u+1, tm+1, tr, p, v);
mn[u] = min(mn[2*u], mn[2*u+1]);
}
}
void set_mx(int u, int tl, int tr, int l, int r, ll v) {
if(tl > r || l > tr) return ;
if(l <= tl && tr <= r) {
pull(u, v);
push(u, tl, tr);
return ;
}
push(u, tl, tr);
int tm = (tl + tr) / 2;
set_mx(2*u, tl, tm, l, r, v);
set_mx(2*u+1, tm+1, tr, l, r, v);
tree[u] = max(tree[2*u], tree[2*u+1]);
}
ll query(int u, int tl, int tr, int l, int r) {
if(tl > r || l > tr) return -inf;
if(l <= tl && tr <= r) return tree[u];
push(u, tl, tr);
int tm = (tl + tr) / 2;
return max(query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r));
}
void set_mn(int p, ll v) { set_mn(1, 1, n, p, v); }
void set_mx(int l, int r, ll v) { set_mx(1, 1, n, l, r, v); }
ll query(int l, int r) { return query(1, 1, n, l, r); }
};
signed main() {
int n; cin >> n;
vector<int> h(n+1), a(n+1), b(n+1), in[2*n+1], out[2*n+1];
for(int i=1; i<=n; i++) cin >> h[i] >> a[i] >> b[i];
int q; cin >> q;
vector<ll> ans(q+1, -1);
vector<pair<int, int> > qus[n+1];
for(int i=1; i<=q; i++) {
int l, r; cin >> l >> r;
qus[r].push_back({ l, i });
}
for(int i=1; i<=n; i++) {
in[i+a[i]].push_back(i);
out[i+b[i]].push_back(i);
}
auto work = [&]() {
segment_tree sgt(n);
for(int i=1; i<=n; i++) {
for(int id : in[i]) sgt.set_mn(id, h[id]);
sgt.set_mx(i-b[i], i-a[i], h[i]);
for(auto [j, id] : qus[i])
ans[id] = max(ans[id], sgt.query(j, i));
for(int id : out[i]) sgt.set_mn(id, 1e18);
}
};
work();
for(int i=1; i<=n; i++) h[i] *= -1;
work();
for(int i=1; i<=q; i++) cout << ans[i] << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |