#include <bits/stdc++.h>
using namespace std;
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
const int MXN = 2e5+5, inf = 1e9;
int n;
int seg[MXN<<2], hseg[MXN<<2], lz[MXN<<2], hlz[MXN<<2];
inline void pull(int id) {
seg[id] = max(seg[lc], seg[rc]);
hseg[id] = max(hseg[lc], hseg[rc]);
}
void build(int l=1, int r=n+1, int id=1) {
lz[id] = 0, hlz[id] = 0;
seg[id] = hseg[id] = -inf;
if(r-l == 1) return;
build(l, mid, lc);
build(mid, r, rc);
}
inline void apply(int x, int hx, int id) {
hseg[id] = max(hseg[id], seg[id]+hx);
seg[id] += x;
hlz[id] = max(hlz[id], lz[id]+hx);
lz[id] += x;
}
inline void push(int id) {
if(lz[id] || hlz[id]) {
apply(lz[id], hlz[id], lc);
apply(lz[id], hlz[id], rc);
lz[id] = hlz[id] = 0;
}
}
void upd(int s, int e, int x, int l=1, int r=n+1, int id=1) {
if(s>=r || l>=e) return;
if(s<=l && r<=e) {
apply(x, max(x, 0), id);
return;
}
push(id);
upd(s, e, x, l, mid, lc);
upd(s, e, x, mid, r, rc);
pull(id);
}
int get(int s, int e, int l=1, int r=n+1, int id=1) {
if(s>=r || l>=e) return -inf;
if(s<=l && r<=e) return hseg[id];
push(id);
return max(get(s, e, l, mid, lc), get(s, e, mid, r, rc));
}
int q, H[MXN], A[MXN], B[MXN], L[MXN], R[MXN], ans[MXN];
vector<int> Q[MXN], add[MXN], rem[MXN];
void solve() {
for(int i=1; i<=q; i++) Q[R[i]].push_back(i);
for(int i=1; i<=n; i++) {
if(i+A[i]<=n) add[i+A[i]].push_back(i);
if(i+B[i]+1<=n) rem[i+B[i]+1].push_back(i);
}
build();
for(int r=1; r<=n; r++) {
for(int i : add[r]) upd(i, i+1, inf-H[i]);
for(int i : rem[r]) upd(i, i+1, -inf+H[i]);
if(r-A[r]>=1) {
upd(max(1, r-B[r]), r-A[r]+1, H[r]);
upd(max(1, r-B[r]), r-A[r]+1, -H[r]);
}
for(int i : Q[r])
ans[i] = max(ans[i], get(L[i], R[i]+1));
}
for(int i=1; i<=n; i++) {
Q[i].clear();
add[i].clear();
rem[i].clear();
}
}
int32_t main() {
cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
for(int i=1; i<=n; i++)
cin >> H[i] >> A[i] >> B[i];
cin >> q;
for(int i=1; i<=q; i++) cin >> L[i] >> R[i], ans[i]=-inf;
solve();
reverse(H+1, H+n+1);
reverse(A+1, A+n+1);
reverse(B+1, B+n+1);
for(int i=1; i<=q; i++) {
L[i] = n+1-L[i];
R[i] = n+1-R[i];
swap(L[i], R[i]);
}
solve();
for(int i=1; i<=q; i++)
cout << (ans[i]==-inf ? -1 : 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... |