Submission #1358254

#TimeUsernameProblemLanguageResultExecution timeMemory
1358254NewtonabcDivide and conquer (IZhO14_divide)C++20
100 / 100
70 ms7120 KiB
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
const int M=1<<18;
ll x[N],g[N],d[N],s[M],arr[N],pd[N],qs[N];
void build(int l,int r,int idx){
    if(l==r){
        s[idx]=LLONG_MIN;
        return;
    }
    int m=(l+r)/2;
    build(l,m,idx*2);
    build(m+1,r,idx*2+1);
    s[idx]=max(s[idx*2],s[idx*2+1]);
}
void update(int l,int r,int idx,int a){
    if(a>r || a<l) return;
    if(l==r){
        s[idx]=arr[l];
        return;
    }
    int m=(l+r)/2;
    update(l,m,idx*2,a);
    update(m+1,r,idx*2+1,a);
    s[idx]=max(s[idx*2],s[idx*2+1]);
}
int walk(int l,int r,int idx,ll val){
    if(l==r) return l;
    int m=(l+r)/2;
    if(s[idx*2+1]>=val) return walk(m+1,r,idx*2+1,val);
    return walk(l,m,idx*2,val);
}
int main(){
    int n; cin>>n;
    for(int i=1;i<=n;i++) cin>>x[i] >>g[i] >>d[i];
    build(1,n,1);
    for(int i=1;i<=n;i++) pd[i]=d[i]+pd[i-1],arr[i]=pd[i]-x[i],qs[i]=g[i]+qs[i-1];
    ll mx=LLONG_MIN;
    // for(int i=1;i<=n;i++) cout<<pd[i] <<" ";
    // cout<<"\n";
    for(int i=n;i>=1;i--){
        update(1,n,1,i);
        int id=walk(1,n,1,pd[i-1]-x[i]);
        ll cd=qs[id]-qs[i-1];
        // cout<<i <<" " <<id <<"\n";
        // cout<<pd[i-1]-x[i]+1LL <<"\n";
        if(cd>mx) mx=cd;
    }
    cout<<mx;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...