#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())
const int INF = 1e9+5;
const int K = 4;
const int MAX = 2e5+1;
int n, L;
int h[MAX], a[MAX], b[MAX], ans[MAX], maxH[MAX], byH[MAX], v[MAX], p[MAX], memo[MAX], lastAdd[MAX];
vector<int> d[MAX];
vector<pair<int, int>> queries[MAX], todo[MAX];
void updV(int i, int val){
v[i] = max(v[i], val);
ans[i/K] = max(ans[i/K], v[i]);
}
void addH(int i){
byH[i] = h[i];
maxH[i/K] = max(maxH[i/K], h[i]);
lastAdd[i/K] = L;
}
void remH(int i){
byH[i] = -INF;
int L = i-(i%K);
maxH[i/K] = -INF;
for(int j = L; j < min(n, i+K); j++){
maxH[i/K] = max(maxH[i/K], byH[j]);
}
if(!d[i/K].empty()){
updV(i, h[i]-h[d[i/K][0]]);
}
}
void add_single(int i){
updV(i, byH[i]-h[L]);
}
void add_to_block(int block){
if(!d[block].empty()){
if(lastAdd[block] != L && h[d[block].back()] <= h[L]) return;
}
while(!d[block].empty() && h[d[block].back()] > h[L]) d[block].pop_back();
d[block].push_back(L);
ans[block] = max(ans[block], maxH[block]-h[L]);
}
int qry(int R){
int res = -INF;
int i = L-(L%K);
while(i+K <= R+1){
res = max(res, ans[i/K]);
i += K;
}
if(i <= R){
int j = 0;
for(; i < min(i+K, n); i++){
int x = p[i];
if(x > R) continue;
res = max(res, v[x]);
if(byH[x] == -INF) continue;
while(j < sz(d[i/K]) && x-a[x] < d[i/K][j]) j++;
if(j < sz(d[i/K])) res = max(res, h[x]-h[d[i/K][j]]);
}
}
return res;
}
void solve(){
for(L = n-1; L >= 0; L--){
for(auto [i, op] : todo[L]){
if(op == 1) addH(i);
else remH(i);
}
int i = L+a[L];
for(; i <= L+b[L] && i % K != 0; i++){
add_single(i);
}
while(i+K-1 <= L+b[L]){
add_to_block(i/K);
i += K;
}
for(; i <= L+b[L]; i++){
add_single(i);
}
for(auto [R, ind] : queries[L]){
memo[ind] = max(memo[ind], qry(R));
}
}
}
void init(){
fill_n(ans, n, -INF);
fill_n(maxH, n, -INF);
fill_n(byH, n, -INF);
fill_n(v, n, -INF);
fill_n(lastAdd, n, n);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
init();
for(int i = 0; i < n; i++){
cin >> h[i] >> a[i] >> b[i];
p[i] = i;
if(i-a[i] >= 0) todo[i-a[i]].emplace_back(i, 1);
if(i-b[i]-1 >= 0) todo[i-b[i]-1].emplace_back(i, -1);
}
for(int i = 0; i < n; i+=K){
int di = min(i+K, n)-i;
sort(p+i, p+i+di, [&](int x, int y){return x-a[x] > y-a[y];});
}
int q;
cin >> q;
fill_n(memo, q, -1);
for(int i = 0; i < q; ++i){
int l, r;
cin >> l >> r;
l--, r--;
queries[l].emplace_back(r, i);
}
solve();
for(int i = 0; i < n; i++) h[i] = -h[i];
init();
solve();
for(int i = 0; i < q; i++) cout << memo[i] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3072 ms |
29740 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
