#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define remove adsfdsfdsf
const ll MAXN=2e5+6;
const ll INF=2e12;
ll n,q,h[MAXN],a[MAXN],b[MAXN];
ll ans[MAXN];
vector<ll>add[MAXN];
vector<ll>remove[MAXN];
vector<pair<ll,ll> >queries[MAXN];
struct segment_tree
{
struct node
{
ll this_val;
ll max_other;
ll max_dif;
};
node tree[4*MAXN];
void init()
{
for(ll i=0;i<4*MAXN;i++)
{
tree[i].this_val=INF;
tree[i].max_other=-INF;
tree[i].max_dif=-INF;
}
}
void recalc(ll idx)
{
tree[idx].max_dif=max(tree[idx].max_dif,tree[idx].max_other-tree[idx].this_val);
}
/*void recalc(node &t)
{
t.max_dif=max(t.max_dif,t.max_other-t.this_val);
}*/
node merge(ll idx1,ll idx2)
{
recalc(idx1);
recalc(idx2);
node ret;
ret.this_val=INF;
ret.max_other=-INF;
ret.max_dif=max(tree[idx1].max_dif,tree[idx2].max_dif);
return ret;
}
void push(ll l,ll r,ll idx)
{
recalc(idx);
if(l!=r)
{
recalc(idx*2);
tree[idx*2].max_other=max(tree[idx*2].max_other,tree[idx].max_other);
recalc(idx*2);
recalc(idx*2+1);
tree[idx*2+1].max_other=max(tree[idx*2+1].max_other,tree[idx].max_other);
recalc(idx*2+1);
}
recalc(idx);
}
void update_this(ll l,ll r,ll idx,ll q,ll val)
{
push(l,r,idx);
if(l>q)return;
if(r<q)return;
if(l==r)
{
recalc(idx);
tree[idx].this_val=val;
tree[idx].max_other=-INF;
recalc(idx);
return;
}
ll mid=(l+r)/2;
update_this(l,mid,idx*2,q,val);
update_this(mid+1,r,idx*2+1,q,val);
tree[idx]=merge(idx*2,idx*2+1);
}
void update_this(ll q,ll val)
{
update_this(1,n,1,q,val);
}
void update_range(ll l,ll r,ll idx,ll ql,ll qr,ll val)
{
push(l,r,idx);
if(l>qr||r<ql)return;
recalc(idx);
if(l>=ql&&r<=qr)
{
tree[idx].max_other=max(tree[idx].max_other,val);
push(l,r,idx);
return;
}
ll mid=(l+r)/2;
update_range(l,mid,idx*2,ql,qr,val);
update_range(mid+1,r,idx*2+1,ql,qr,val);
tree[idx]=merge(idx*2,idx*2+1);
}
void update_range(ll ql,ll qr,ll val)
{
update_range(1,n,1,ql,qr,val);
}
ll query(ll l,ll r,ll idx,ll ql,ll qr)
{
push(l,r,idx);
if(l>qr||r<ql)return -INF;
if(l>=ql&&r<=qr)return tree[idx].max_dif;
ll mid=(l+r)/2;
return max(query(l,mid,idx*2,ql,qr),query(mid+1,r,idx*2+1,ql,qr));
}
ll query(ll ql,ll qr)
{
return query(1,n,1,ql,qr);
}
}t;
void solve()
{
t.init();
for(ll i=1;i<=n;i++)
{
for(auto xd:add[i])
{
//cout<<"add1 "<<xd<<endl;
t.update_this(xd,h[xd]);
}
ll l=i-b[i];
ll r=i-a[i];
l=max(1ll,l);
if(l<=r)
{
//cout<<"add2 "<<i<<" "<<l<<" "<<r<<endl;
t.update_range(l,r,h[i]);
}
for(auto xd:queries[i])
{
ans[xd.second]=max(ans[xd.second],t.query(xd.first,i));
}
for(auto xd:remove[i])
{
//cout<<"remove1 "<<xd<<endl;
t.update_this(xd,INF);
}
}
}
void read()
{
cin>>n;
for(ll i=1;i<=n;i++)
{
cin>>h[i]>>a[i]>>b[i];
}
cin>>q;
for(ll i=1;i<=q;i++)
{
ll l,r;
cin>>l>>r;
ans[i]=-1;
queries[r].push_back({l,i});
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
read();
for(ll i=1;i<=n;i++)
{
if(i+a[i]>n)continue;
remove[min(n,i+b[i])].push_back(i);
add[i+a[i]].push_back(i);
}
solve();
for(ll i=1;i<=n;i++)h[i]=-h[i];
/*for(ll i=1;i<=q;i++)
{
cout<<ans[i]<<endl;
}*/
solve();
for(ll i=1;i<=q;i++)
{
cout<<ans[i]<<endl;
}
return 0;
}
/*
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
24 ms |
33280 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
24 ms |
33280 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
621 ms |
45156 KB |
Output is correct |
2 |
Correct |
706 ms |
46820 KB |
Output is correct |
3 |
Correct |
468 ms |
42724 KB |
Output is correct |
4 |
Incorrect |
719 ms |
46624 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
24 ms |
33280 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |