#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
const int N=1e6 + 5;
const int M=3e5 + 5;
ll a[M],b[M];
ll tree[4*N],arr[N],lazy[4*N];
ll x[N], g[N], d[N], gg[N], dd[N];
void build(int node,int start,int end)
{
if(start==end){
tree[node]=arr[start];
return ;
}
int mid=(start+end)/2;
build(2*node+1,start,mid);
build(2*node+2,1+mid,end);
tree[node]=max(tree[2*node+1],tree[2*node+2]);
}
void update(int node,int start,int end,int l,int r,ll val)
{
if(lazy[node]!=0){
ll foo=lazy[node];
lazy[node]=0;
tree[node]+=foo;
if(start!=end){
lazy[2*node+1]+=foo;
lazy[2*node+2]+=foo;
}
}
if(end<l || start>r) return ;
if(start>=l && end<=r){
tree[node]+=val;
if(start!=end){
lazy[2*node+1]+=val;
lazy[2*node+2]+=val;
}
return ;
}
int mid=(start+end)/2;
update(2*node+1,start,mid,l,r,val);
update(2*node+2,1+mid,end,l,r,val);
tree[node]=max(tree[2*node+1],tree[2*node+2]);
}
ll quer(int node,int start,int end,int l,int r)
{
if(lazy[node]!=0){
ll foo=lazy[node];
lazy[node]=0;
tree[node]+=foo;
if(start!=end){
lazy[2*node+1]+=foo;
lazy[2*node+2]+=foo;
}
}
if(end<l || start>r) return -1e17 ;
if(start>=l && end<=r){
return tree[node];
}
int mid=(start+end)/2;
return ( max(quer(2*node+1,start,mid,l,r) , quer(2*node+2,1+mid,end,l,r)));
}
ll quer2(int node, int start, int end)
{
if(lazy[node]!=0){
ll foo=lazy[node];
lazy[node]=0;
tree[node]+=foo;
if(start!=end){
lazy[2*node+1]+=foo;
lazy[2*node+2]+=foo;
}
}
if(start==end){
if(tree[node]>=0)
return start;
else
return -1;
}
int mid = (start+end)/2;
ll foo = tree[2*node+1]+lazy[2*node+1];
ll bar = tree[2*node+2]+lazy[2*node+2];
if(bar>=0){
return quer2(2*node+2,mid+1,end);
}
else{
return quer2(2*node+1,start,mid);
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
int i;
for(i=0;i<N;i++){
lazy[i]=0;
arr[i]=0;
}
int n,m;
cin>>n;
int ans=0;
for(int i=0;i<n;i++)
{
cin>>x[i]>>g[i]>>d[i];
gg[i]=g[i]; dd[i] = d[i];
ans = max( ans, g[i]);
if(i)
{
g[i]+=g[i-1];
d[i]+=d[i-1];
}
x[i]-=x[0];
}
for(i=0;i<n;i++){
arr[i]=d[i]-x[i];
// cout<<arr[i]<<" ";
}
//cout<<endl;
build(0,0,n-1);
for(int i=0;i<n;i++)
{
// cout<<quer(0,0,n-1,i,i)<<endl;
// cout<<quer2(0,0,n-1)<<endl;
int x= quer2(0,0,n-1);
if(x<0)
continue;
int temp= g[x];
if(i)
temp-=g[i-1];
ans = max(ans, temp);
if(i!=n-1)
{
int nextd = d[i+1]-d[i];
int temp = nextd - dd[i];
update(0,0,n-1,i+1,n-1,temp);
}
update(0,0,n-1,i,i,-1e17);
}
cout<<ans<<endl;
return 0;
}
Compilation message
divide.cpp: In function 'long long int quer2(long long int, long long int, long long int)':
divide.cpp:90:12: warning: unused variable 'foo' [-Wunused-variable]
ll foo = tree[2*node+1]+lazy[2*node+1];
^~~
divide.cpp: In function 'int32_t main()':
divide.cpp:109:15: warning: unused variable 'm' [-Wunused-variable]
int n,m;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
16000 KB |
Output is correct |
| 2 |
Incorrect |
15 ms |
16128 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
16000 KB |
Output is correct |
| 2 |
Correct |
14 ms |
16000 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
16000 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
16380 KB |
Output is correct |
| 2 |
Correct |
23 ms |
16692 KB |
Output is correct |
| 3 |
Correct |
22 ms |
16640 KB |
Output is correct |
| 4 |
Correct |
47 ms |
19168 KB |
Output is correct |
| 5 |
Correct |
49 ms |
19192 KB |
Output is correct |
| 6 |
Correct |
89 ms |
22008 KB |
Output is correct |
| 7 |
Correct |
81 ms |
22136 KB |
Output is correct |
| 8 |
Correct |
86 ms |
22008 KB |
Output is correct |
| 9 |
Correct |
81 ms |
22008 KB |
Output is correct |
| 10 |
Incorrect |
48 ms |
22012 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
