#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2e5+5;
long long seg[4*MAXN];
long long temph[4*MAXN];
long long n,q;
long long lazy[4*MAXN];
long long h[MAXN];
long long a[MAXN];
long long ans[MAXN];
long long b[MAXN];
vector<int> add[MAXN];
vector<int> rem[MAXN];
vector<pair<int,int>> v1[MAXN];
bool nxt = false;
void build(long long curr,long long l,long long r){
if(l==r){
seg[curr] =-987654321987654321;
lazy[curr] =-987654321987654321;
temph[curr] = 987654321987654321;
return;
}
long long mid = (l+r)/2;
build(2*curr,l,mid);
build(2*curr+1,mid+1,r);
seg[curr] = max(seg[2*curr],seg[2*curr+1]);
lazy[curr] = max(lazy[2*curr],lazy[2*curr+1]);
temph[curr] = min(temph[2*curr],temph[2*curr+1]);
}
void pushdown(long long curr,long long l,long long r){
lazy[2*curr] = max(lazy[curr],lazy[2*curr]);
lazy[2*curr+1] = max(lazy[curr],lazy[2*curr+1]);
seg[2*curr] = max(seg[2*curr],lazy[2*curr]-temph[2*curr]);
seg[2*curr+1] = max(seg[2*curr+1],lazy[2*curr+1]-temph[2*curr+1]);
lazy[curr] = -987654321987654321;
}
void pointupdate(long long curr,long long l,long long r,long long ind,long long x){
if(l==r){
temph[curr] = x;
lazy[curr] = -987654321987654321;
return;
}
pushdown(curr,l,r);
long long mid = (l+r)/2;
if(ind<=mid){
pointupdate(2*curr,l,mid,ind,x);
}else{
pointupdate(2*curr+1,mid+1,r,ind,x);
}
seg[curr] = max(seg[2*curr],seg[2*curr+1]);
temph[curr] = min(temph[2*curr],temph[2*curr+1]);
if(curr == 4){
//cout<<ind<<" "<<x<<" "<<temph[curr]<<" "<<temph[2*curr]<<" "<<temph[2*curr+1]<<endl;
}
}
void rangeupdate(long long curr,long long l,long long r,long long tl,long long tr,long long val){
if(l>tr||r<tl){
return;
}
if(tl<=l && r<=tr){
lazy[curr] = max(lazy[curr],val);
seg[curr] = max(seg[curr],val-temph[curr]);
// cout<<curr<<" "<<123<<" "<<l<<" "<<r<<" "<<temph[2*2*curr]<<endl;
return;
}
long long mid =(l+r)/2;
pushdown(curr,l,r);
rangeupdate(2*curr,l,mid,tl,tr,val);
rangeupdate(2*curr+1,mid+1,r,tl,tr,val);
seg[curr] = max(seg[2*curr],seg[2*curr+1]);
}
long long query(long long curr,long long l,long long r,long long tl,long long tr){
// cout<<l<<" "<<r<<endl;
if(l>tr||r<tl){
return -987654321987654321;
}
if(tl<=l &&r<=tr){
return seg[curr];
}
pushdown(curr,l,r);
long long mid = (l+r)/2;
return max(query(2*curr,l,mid,tl,tr),query(2*curr+1,mid+1,r,tl,tr));
}
int main(){
cin>>n;
for(long long i=1;i<=n;i++){
cin>>h[i]>>a[i]>>b[i];
if(a[i]+i<MAXN){
add[a[i]+i].push_back(i);
}
if(b[i]+i+1<MAXN){
rem[b[i]+i+1].push_back(i);
}
//cout<<a[i]+i<<" "<<b[i]+i+1<<endl;
ans[i] = -1;
}
cin>>q;
for(long long i=1;i<=q;i++){
long long l,r;
cin>>l>>r;
v1[r].push_back(make_pair(l,i));
}
build(1,1,n);
// cout<<query(1,1,n,1,2)<<endl;
for(long long i=1;i<=n;i++){
for(long long x:add[i]){
pointupdate(1,1,n,x,h[x]);
}
for(long long x:rem[i]){
pointupdate(1,1,n,x,987654321987654321);
}
//cout<<123<<endl;
if(i-a[i]>=1){
rangeupdate(1,1,n,max((long long)1,i-b[i]),i-a[i],h[i]);
// cout<<" "<<max((long long)1,i-b[i])<<" "<<i-a[i]<<" "<<h[i]<<endl;
}
for(auto x:v1[i]){
//
ans[x.second] = max(ans[x.second],query(1,1,n,x.first,i));
// cout<<x.first<<" "<<i<<" "<<query(1,1,n,x.first,i)<<endl;
}
// cout<<query(1,1,n,1,20)<<endl;
}
//reverse
//cout<<ans[1]<<endl;
build(1,1,n);
// cout<<query(1,1,n,1,2)<<endl;
for(long long i=1;i<=n;i++){
h[i] = 1000000000-h[i];
}
nxt = true;
for(long long i=1;i<=n;i++){
for(long long x:add[i]){
// cout<<h[x]<<endl;
pointupdate(1,1,n,x,h[x]);
}
for(long long x:rem[i]){
pointupdate(1,1,n,x,987654321987654321);
}
//cout<<123<<endl;
if(i-a[i]>=1){
rangeupdate(1,1,n,max((long long)1,i-b[i]),i-a[i],h[i]);
//cout<<" "<<max(1,i-b[i])<<" "<<i-a[i]<<endl;
}
for(auto x:v1[i]){
// cout<<ans[x.second]<<endl;
ans[x.second] = max(ans[x.second],query(1,1,n,x.first,i));
// cout<<x.first<<" "<<i<<" "<<query(1,1,n,x.first,i)<<endl;
}
}
/*for(long long i=n;i>=1;i--){
for(long long x:rem[i+1]){
pointupdate(1,1,n,x,h[x]);
}
for(long long x:add[i+1]){
pointupdate(1,1,n,x,-987654321987654321);
}
if(i+a[i]<=n){
rangeupdate(1,1,n,i+a[i],max(i+b[i],n),h[i]);
}
for(auto x:v1[i]){
ans[x.second] = max(ans[x.second],query(1,1,n,x.first,i));
}
} */
for(long long i=1;i<=q;i++){
cout<<ans[i]<<endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14464 KB |
Output is correct |
2 |
Correct |
13 ms |
14592 KB |
Output is correct |
3 |
Incorrect |
14 ms |
14464 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14464 KB |
Output is correct |
2 |
Correct |
13 ms |
14592 KB |
Output is correct |
3 |
Incorrect |
14 ms |
14464 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
604 ms |
40440 KB |
Output is correct |
2 |
Correct |
664 ms |
41080 KB |
Output is correct |
3 |
Correct |
463 ms |
38904 KB |
Output is correct |
4 |
Correct |
648 ms |
41160 KB |
Output is correct |
5 |
Correct |
296 ms |
29620 KB |
Output is correct |
6 |
Correct |
662 ms |
41208 KB |
Output is correct |
7 |
Correct |
577 ms |
40176 KB |
Output is correct |
8 |
Correct |
670 ms |
41172 KB |
Output is correct |
9 |
Correct |
94 ms |
19192 KB |
Output is correct |
10 |
Correct |
676 ms |
41208 KB |
Output is correct |
11 |
Correct |
422 ms |
32120 KB |
Output is correct |
12 |
Correct |
662 ms |
41160 KB |
Output is correct |
13 |
Correct |
480 ms |
38688 KB |
Output is correct |
14 |
Correct |
467 ms |
38648 KB |
Output is correct |
15 |
Correct |
462 ms |
38740 KB |
Output is correct |
16 |
Correct |
444 ms |
39160 KB |
Output is correct |
17 |
Correct |
485 ms |
38944 KB |
Output is correct |
18 |
Correct |
470 ms |
39160 KB |
Output is correct |
19 |
Correct |
482 ms |
38484 KB |
Output is correct |
20 |
Correct |
477 ms |
38720 KB |
Output is correct |
21 |
Correct |
450 ms |
38564 KB |
Output is correct |
22 |
Correct |
467 ms |
38976 KB |
Output is correct |
23 |
Correct |
475 ms |
38772 KB |
Output is correct |
24 |
Correct |
443 ms |
38776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14464 KB |
Output is correct |
2 |
Correct |
13 ms |
14592 KB |
Output is correct |
3 |
Incorrect |
14 ms |
14464 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |