#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef int64_t ll;
#define sow cerr<<"here"<<endl;
const int inf = 1e9 + 5;
const int N = 2e5 + 5;
const int B = 450;
const int B_ = N / B + 1;
struct ST{
int mx[B << 2], mn[B << 2];
ST(){
for(int i=0;i<(B << 2);i++) mn[i] = inf, mx[i] = -inf;
}
void set(int i, int v, int lx = 0, int rx = N, int x = 1){
if(lx == rx){
if(v == -1) mn[x] = inf, mx[x] = -inf;
else mn[x] = mx[x] = v;
return;
} int m = (lx + rx) >> 1;
if(i <= m) set(i, v, lx, m, x << 1);
else set(i, v, m + 1, rx, x << 1 | 1);
mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}
ar<int, 2> get(int l, int r, int lx = 0, int rx = N, int x = 1){
if(lx > r || rx < l){
return {inf, -inf};
} if(lx >= l && rx <= r){
return {mn[x], mx[x]};
} int m = (lx + rx) >> 1;
auto L = get(l, r, lx, m, x << 1), R = get(l, r, m + 1, rx, x << 1 | 1);
return {min(L[0], R[0]), max(L[1], R[1])};
}
}tree;
vector<int> Q[N];
int pref[B_][N], suff[B_][N];
int h[N], a[N], b[N];
int l[N], r[N], ans[B_][B][B];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
for(int i=0;i<n;i++){
cin >> h[i] >> a[i] >> b[i];
}
int q; cin >> q;
for(int i=0;i<q;i++){
cin >> l[i] >> r[i];
}
memset(pref, -1, sizeof pref);
memset(suff, -1, sizeof suff);
memset(ans, -1, sizeof ans);
for(int g=0;g * B<n;g++){
int L = g * B, R = min(n, (g + 1) * B);
vector<ar<int, 2>> t;
for(int i=L;i<R;i++){
t.push_back({i + a[i], i + 1});
t.push_back({i + b[i] + 1, -i - 1});
}
sort(t.begin(), t.end());
multiset<int> ss;
int j = 0;
for(int i=L;i<n;i++){
while(j < (int)t.size() && t[j][0] <= i){
if(t[j][1] > 0){
ss.insert(h[t[j][1] - 1]);
} else {
ss.erase(ss.find(h[-t[j][1] - 1]));
} j++;
}
if(i) pref[g][i] = pref[g][i-1];
if(i - b[i] <= L && R - 1 <= i - a[i]){
if(!ss.empty()){
pref[g][i] = max(pref[g][i], abs(*--ss.end() - h[i]));
pref[g][i] = max(pref[g][i], abs(*ss.begin() - h[i]));
}
} else {
int l_ = max(i - b[i], L), r_ = min(i - a[i], R - 1);
for(int j=l_;j<=r_;j++){
if(j + a[j] <= i && i <= j + b[j]){
pref[g][i] = max(pref[g][i], abs(h[i] - h[j]));
}
}
}
}
t.clear();
for(int i=L;i<R;i++){
t.push_back({i - a[i], i + 1});
t.push_back({i - b[i] - 1, -i - 1});
}
sort(t.rbegin(), t.rend());
ss.clear(), j = 0;
for(int i=R-1;~i;i--){
while(j < (int)t.size() && t[j][0] >= i){
if(t[j][1] > 0){
ss.insert(h[t[j][1] - 1]);
} else {
ss.erase(ss.find(h[-t[j][1] - 1]));
} j++;
}
suff[g][i] = suff[g][i+1];
if(i + a[i] <= L && R - 1 <= i + b[i]){
if(!ss.empty()){
suff[g][i] = max(suff[g][i], abs(*--ss.end() - h[i]));
suff[g][i] = max(suff[g][i], abs(*ss.begin() - h[i]));
}
} else {
int l_ = max(i + a[i], L), r_ = min(i + b[i], R - 1);
for(int j=l_;j<=r_;j++){
if(j - b[j] <= i && i <= j - a[j]){
suff[g][i] = max(suff[g][i], abs(h[i] - h[j]));
}
}
}
}
for(int i=R-1;i>=L;i--){
//~ seg[0][g][i-L][i-L] = seg[1][g][i-L][i-L] = h[i];
for(int j=i+1;j<R;j++){
//~ seg[0][g][i-L][j-L] = min(seg[0][g][i-L][j-L-1], h[j]);
//~ seg[1][g][i-L][j-L] = max(seg[1][g][i-L][j-L-1], h[j]);
ans[g][i-L][j-L] = max(ans[g][i+1-L][j-L], ans[g][i-L][j-L-1]);
if(i + a[i] <= j && j <= i + b[i] && j - b[j] <= i && i <= j - a[j]){
ans[g][i-L][j-L] = max(ans[g][i-L][j-L], abs(h[i] - h[j]));
}
}
}
}
for(int j=0;j<q;j++){
l[j]--, r[j]--;
int bl = l[j] / B, br = r[j] / B, res = -1;
if(bl == br){
int L = bl * B;
cout<<ans[bl][l[j] - L][r[j] - L]<<"\n";
continue;
}
for(int i=bl + 1;i<br;i++){
res = max(res, pref[i][r[j]]);
res = max(res, suff[i][l[j]]);
}
res = max(res, pref[br][r[j]]);
res = max(res, suff[bl][l[j]]);
int L = br * B, R = (bl + 1) * B - 1;
for(int i=l[j];i<=R;i++){
int l_ = max(i + a[i], L), r_ = min(i + b[i], r[j]);
if(l_ <= r_){
Q[l_].push_back(i);
//~ res = max(res, abs(h[i] - seg[0][br][l_-L][r_-L]));
//~ res = max(res, abs(h[i] - seg[1][br][l_-L][r_-L]));
Q[r_ + 1].push_back(-i - 1);
}
}
for(int i=L;i<=r[j];i++){
for(auto k : Q[i]){
if(k >= 0) tree.set(k - l[j], h[k]);
else tree.set(-k - 1 - l[j], -1);
} Q[i].clear();
int l_ = max(i - b[i], l[j]), r_ = min(i - a[i], R);
if(l_ <= r_){
auto sg = tree.get(l_ - l[j], r_ - l[j]);
if(sg[1] >= 0){
res = max({res, abs(h[i] - sg[0]), abs(h[i] - sg[1])});
}
}
}
for(auto k : Q[r[j] + 1]){
if(k >= 0) tree.set(k - l[j], h[k]);
else tree.set(-k - 1 - l[j], -1);
} Q[r[j] + 1].clear();
cout<<res<<"\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
191 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
191 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
240 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
191 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
