This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int inf = 1e9 + 100;
int n, Q;
///SEGMENT TREE BEGIN
struct node{
int s, e, m, C, lazy, D;
node *l, *r;
node(int _s, int _e){
s = _s; e = _e;
m = (s+e)/2;
C = -inf, lazy = inf, D = -inf;
if(s != e){
l = new node(s, m);
r = new node(m+1, e);
}
}
void push(){
if(lazy != inf){
l->lazy = min(l->lazy, lazy);
r->lazy = min(r->lazy, lazy);
l->D = max(l->D, l->C - lazy);
r->D = max(r->D, r->C - lazy);
lazy = inf;
}
}
void pull(){
C = max(l->C, r->C);
D = max(l->D, r->D);
}
void updateC(int i, int H){
if(s == e){
C = H;
return;
}
push();
if(i <= m) l->updateC(i, H);
else r->updateC(i, H);
pull();
}
void updateLazy(int L, int R, int H){
if(s == L && e == R){
D = max(D, C - H);
lazy = min(lazy, H);
return;
}
push();
if(R <= m) l->updateLazy(L, R, H);
else if(L >= m+1) r->updateLazy(L, R, H);
else{
l->updateLazy(L, m, H);
r->updateLazy(m+1, R, H);
}
pull();
}
int query(int L, int R){
//if(s == 0 && e == n-1) cout << "Q: " << L << " " << R <<"\n";
if(s == L && e == R) return D;
push();
if(R <= m) return l->query(L, R);
else if(L >= m+1) return r->query(L, R);
else{
return max(l->query(L, m), r->query(m+1, R));
}
}
} *root;
///SEGMENT TREE END
int H[200005];
int A[200005];
int B[200005];
int ans[200005];
ii QQ[200005];
vector<ii> queries[200005];
vector<ii> events[200005];
void solve(){
for(int i = 0;i < n;i++) events[i].clear();
for(int i = 0;i < n;i++) queries[i].clear();
root = new node(0, n-1);
for(int i = 0;i < n;i++){
int start = i + A[i], end = i + B[i] + 1;
if(start < n) events[start].push_back(ii(i, 1)); ///1 is start
if(end < n) events[end].push_back(ii(i, -1)); ///-1 is end
}
for(int i = 0;i < Q;i++){
queries[QQ[i].second].push_back(ii(QQ[i].first, i));
}
for(int r = 0;r < n;r++){
//cout << r << ":\n";
sort(events[r].begin(),events[r].end());
for(ii e : events[r]){
if(e.second == 1) root->updateC(e.first, H[e.first]);
else root->updateC(e.first, -inf);
}
if(r - A[r] >= 0){
int R = r - A[r];
int L = max(0, r - B[r]);
root->updateLazy(L, R, H[r]);
}
for(ii q : queries[r]){
int res = root->query(q.first, r);
//cout << q.second << " " << q.first << " " << r << " " << res << "\n";
ans[q.second] = max(ans[q.second],res);
}
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 0;i < n;i++) cin >> H[i] >> A[i] >> B[i];
cin >> Q;
fill(ans,ans+Q, -inf);
for(int i = 0;i < Q;i++){
int l, r; cin >> l >> r; l--; r--;
QQ[i] = ii(l,r);
}
solve();
reverse(H,H+n);
reverse(A,A+n);
reverse(B,B+n);
for(int i = 0;i < Q;i++){
QQ[i].first = n - 1 - QQ[i].first;
QQ[i].second = n - 1 - QQ[i].second;
swap(QQ[i].first,QQ[i].second);
}
solve();
for(int i = 0;i < Q;i++) cout << max(-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... |