#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2e5 + 5;
const ll inf = 1e18;
ll n, h[NMAX], a[NMAX], b[NMAX], Q, ans[NMAX], l[NMAX], r[NMAX], base = 1, s, e;
vector<ll> p[NMAX], m[NMAX];
vector<pair<ll, ll>> query[NMAX];
vector<ll> c, d, lazy;
void init() {
for (int i = 1; i <= n + 1; i++) {
p[i].clear();
m[i].clear();
}
for (int i = 1; i < base * 2; i++) c[i] = inf, d[i] = -inf, lazy[i] = -1;
return;
}
void upd_lazy(ll idx) {
if (lazy[idx] == -1) return;
d[idx] = max(d[idx], lazy[idx] - c[idx]);
if (idx < base) {
lazy[idx * 2] = max(lazy[idx * 2], lazy[idx]);
lazy[idx * 2 + 1] = max(lazy[idx * 2 + 1], lazy[idx]);
}
lazy[idx] = -1;
return;
}
void updc(ll idx, ll v) {
idx += base;
upd_lazy(idx);
c[idx] = v; idx /= 2;
while (idx) {
upd_lazy(idx);
c[idx] = min(c[idx * 2], c[idx * 2 + 1]);
idx /= 2;
}
return;
}
ll minc(ll l, ll r) {
ll ret = inf;
l += base; r += base;
while (l <= r) {
if (l & 1) ret = min(ret, c[l++]);
if (!(r & 1)) ret = min(ret, c[r--]);
l /= 2; r /= 2;
}
return ret;
}
void updd(ll idx, ll nl, ll nr, ll l, ll r, ll v) {
upd_lazy(idx);
if (nr < l || nl > r) return;
if (nl >= l && nr <= r) {
d[idx] = max(d[idx], v - c[idx]);
if (nl != nr) {
lazy[idx * 2] = max(lazy[idx * 2], v);
lazy[idx * 2 + 1] = max(lazy[idx * 2 + 1], v);
}
return;
}
ll mid = (nl + nr) / 2;
updd(idx * 2, nl, mid, l, r, v);
updd(idx * 2 + 1, mid + 1, nr, l, r, v);
d[idx] = max(d[idx * 2], d[idx * 2 + 1]);
return;
}
ll mxd(ll idx, ll nl, ll nr, ll l, ll r) {
upd_lazy(idx);
if (nr < l || nl > r) return -inf;
if (nl >= l && nr <= r) return d[idx];
ll mid = (nl + nr) / 2;
return max(mxd(idx * 2, nl, mid, l, r), mxd(idx * 2 + 1, mid + 1, nr, l, r));
}
void go() {
init();
for (int i = 1; i <= n; i++) {
s = min(i + a[i], n);
e = min(i + b[i] + 1, n + 1);
p[s].emplace_back(i);
m[e].emplace_back(i);
for (ll x : p[i]) updc(x, h[x]);
for (ll x : m[i]) updc(x, inf);
if (i > 1) {
s = max(i - b[i], 1LL);
e = max(i - a[i], 1LL);
updd(1, 0, base - 1, s, e, h[i]);
for (auto& q : query[i])
ans[q.second] = max(ans[q.second], mxd(1, 0, base - 1, q.first, i));
}
}
return;
}
int main(void) {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
while (base < n + 1) base *= 2;
c.resize(base * 2); d.resize(base * 2); lazy.resize(base * 2);
for (int i = 1; i <= n; i++) cin >> h[i] >> a[i] >> b[i];
cin >> Q;
for (int i = 0; i < Q; i++) {
cin >> l[i] >> r[i];
query[r[i]].emplace_back(l[i], i);
ans[i] = -inf;
}
go();
reverse(h + 1, h + n + 1);
reverse(a + 1, a + n + 1);
reverse(b + 1, b + n + 1);
for (int i = 1; i <= n; i++) query[i].clear();
for (int i = 0; i < Q; i++) {
l[i] = n + 1 - l[i];
r[i] = n + 1 - r[i];
swap(l[i], r[i]);
query[r[i]].emplace_back(l[i], i);
}
go();
for (int i = 0; i < Q; i++) {
if (ans[i] < 0) cout << "-1\n";
else cout << ans[i] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
541 ms |
42100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
