#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<>,
rb_tree_tag, tree_order_statistics_node_update>
ordered_set;
#define ll long long
#define ii pair<ll,ll>
#define iii tuple<ll,ll,ll>
#ifndef DEBUG
#define cerr if (0) cerr
#define endl '\n'
#endif
const ll inf=1e15;
const ll maxn=2e5+5;
const ll mod=1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll arr[maxn],brr[maxn],crr[maxn];
ll pref[maxn];
ll bpref[maxn];
struct node{
ll s,e,m,val;
node *l, *r;
node(ll _s, ll _e){
s=_s,e=_e,m=(s+e)>>1,val=0;
if (s!=e) l=new node(s,m),r=new node(m+1,e);
}
void upd(ll x, ll v){
if (s==e){
val=v;
return;
}
if (x>m) r->upd(x,v);
else l->upd(x,v);
val=max(l->val,r->val);
}
ll query(ll x, ll y){
if (x<=s && e<=y) return val;
if (x>m) return r->query(x,y);
if (y<=m) return l->query(x,y);
return max(l->query(x,y),r->query(x,y));
}
}*root;
ll n;
ll find(ll x, ll s){
ll l=s,r=n+1,m; //left is legal for sure
while (l!=r-1){
m=(l+r)>>1;
if (root->query(m,n)>=x) l=m;
else r=m;
}
return l;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin>>n;
root=new node(1,n);
for (int i=1;i<=n;i++){
cin>>arr[i]>>brr[i]>>crr[i];
}
pref[1]=crr[1];
root->upd(1,pref[1]);
bpref[1]=brr[1];
for (int i=2;i<=n;i++){
pref[i]=pref[i-1]+crr[i]-(arr[i]-arr[i-1]);
cerr<<pref[i]<<endl;
root->upd(i,pref[i]);
//difference between length and cover
bpref[i]=brr[i]+bpref[i-1];
}
ll tot=0,ans=0; //minimally more than this
for (int i=1;i<=n;i++){
ll res=find(tot,i);
ans=max(bpref[res]-bpref[i-1],ans);
tot=pref[i];
cerr<<tot<<endl;
}
cout<<ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
6492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
