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>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pll pair<ll,ll>
#define y1 Enkognit
#define fi first
#define se second
#define pld pair<ld,ld>
using namespace std;
const ll MOD=1000000007;
ll l, r, n, m, k, y, leaf[10000001], a[1000001], x[1000001], b[1000001];
ll tt[10000001];
vector <ll> an;
ll binpow(ll h,ll r)
{
ll l=1;
while (r)
{
if (r&1) l*=h,l%=MOD;
h*=h;
h%=MOD;
r/=2;
}
return l;
}
ll d[10000001];
void push(int h)
{
if (leaf[h]) return;
if (tt[h])
{
d[h*2]+=tt[h];
tt[h*2]+=tt[h];
d[h*2+1]+=tt[h];
tt[h*2+1]+=tt[h];
tt[h]=0;
}
}
void build(int h,int l,int r)
{
if (l==r) {leaf[h]=1;d[h]=-1;return;}
int w=(l+r)/2;
build(h*2,l,w);
build(h*2+1,w+1,r);
d[h]=-1;
}
void update(int h,int l,int r,int x,int y,int k)
{
//cout << l << " " << x << " " << y << " " << r << "\n";
push(h);
if (x>y) return;
if (l==x && y==r)
{
d[h]+=k;
tt[h]+=k;
push(h);
return;
}
int w=(l+r)/2;
update(h*2,l,w,x,min(y,w),k);
update(h*2+1,w+1,r,max(x,w+1),y,k);
d[h]=max(d[h*2],d[h*2+1]);
}
ll get(int h,int l,int r)
{
push(h);
if (l==r) return l;
int w=(l+r)/2;
if (d[h*2]>=0) return get(h*2,l,w); else return get(h*2+1,w+1,r);
}
int main()
{
//ios::sync_with_stdio(0);
cin >> n;
for (ll i = 1; i <= n; i++)
{
cin >> x[i] >> b[i] >> a[i];
b[i]+=b[i-1];
}
ll ans=0;
build(1,1,n);
for (int i = 1; i <= n; i++)
{
update(1,1,n,i,i,1);
//cout << i << "\n";
update(1,1,n,1,i,a[i]);
update(1,1,n,1,i-1,x[i-1]-x[i]);
ans=max(ans,b[i]-b[get(1,1,n)-1]);
}
cout << ans;
return 0;
}
/*
4
0 5 1
1 7 2
4 4 1
7 15 1
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |