#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);
}*/
void push(ll idx)
{
recalc(idx);
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);
}
node merge(ll idx1,ll idx2)
{
push(idx1/2);
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);
if(l!=r)tree[idx]=merge(idx*2,idx*2+1);
}
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);
//cout<<l<<" "<<r<<" "<<idx<<endl;
if(l>qr||r<ql)return -INF;
if(l>=ql&&r<=qr)
{
//cout<<l<<" "<<r<<" "<<idx<<" "<<tree[idx].max_dif<<endl;
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);
}
void print(ll l,ll r,ll idx)
{
cout<<l<<" "<<r<<" "<<idx<<":\n";
cout<<tree[idx].this_val<<" "<<tree[idx].max_other<<" "<<tree[idx].max_dif<<endl;
if(l!=r)print(l,(l+r)/2,idx*2);
if(l!=r)print((l+r)/2+1,r,idx*2+1);
}
}t;
void solve()
{
t.init();
for(ll i=1;i<=n;i++)
{
/*cout<<"----------------";
cout<<"\n";
cout<<" "<<i<<"\n";
cout<<"\n";*/
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]);
}
//t.print(1,n,1);
/*for(int j=1;j<=i;j++)
{
cout<<"query "<<j<<" "<<i<<" "<<t.query(j,i)<<endl;
}
for(int j=1;j<i;j++)
{
cout<<"query "<<j<<" "<<i-1<<" "<<t.query(j,i-1)<<endl;
}*/
for(auto xd:queries[i])
{
//cout<<"query "<<xd.first<<" "<<i<<endl;
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);
}
//t.print(1,n,1);
}
}
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 |
33260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
33260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
944 ms |
45216 KB |
Output is correct |
| 2 |
Correct |
1129 ms |
45984 KB |
Output is correct |
| 3 |
Correct |
730 ms |
42596 KB |
Output is correct |
| 4 |
Correct |
1104 ms |
45992 KB |
Output is correct |
| 5 |
Incorrect |
445 ms |
39400 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
24 ms |
33260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
