Submission #1186783

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186783		FaresSTH	Divide and conquer (IZhO14_divide)	C++20	100 / 100	282 ms	9232 KiB

divide

#include "bits/stdc++.h"
using namespace std;
using ll=long long;
#define S second
#define F first
vector<pair<ll,ll>>tree;
ll N;
void init(ll n){
    N=1<<(ll)ceil(log2(n));
    tree.resize(N*2,{ll(0),ll(-1e18)});
}
pair<ll,ll>merge(pair<ll,ll>v1,pair<ll,ll>v2){
    return {v1.F+v2.F,max(v1.S,v1.F+v2.S)};
}
void upd(ll id,pair<ll,ll>val){
    id+=N;
    tree[id]=val;
    while(id/=2)tree[id]=merge(tree[id*2],tree[id*2+1]);
}
pair<ll,ll>query(ll id,ll l,ll r,ll s,ll e){
    if(s<=l&&r<=e)return tree[id];
    if(l>e||r<s)return {ll(0),ll(-1e18)};
    int m=(l+r)/2;
    return merge(query(id*2,l,m,s,e),query(id*2+1,m+1,r,s,e));
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>>n;
    init(n);
    vector<array<ll,3>>a(n);
    ll pg[n],pe[n],res=0;

    for(int i=0;i<n;i++){
        cin>>a[i][0]>>a[i][1]>>a[i][2];
        pg[i]=a[i][1];
        pe[i]=a[i][2];
        if(i){
            pg[i]=pg[i-1]+a[i][1];
            pe[i]=pe[i-1]+a[i][2];
        }
        res=max(res,a[i][1]);
    }
    ll pr[n]; pr[0]=0;
    for(int i=1;i<n;i++){
        upd(i,{a[i][2]-a[i][0]+a[i-1][0],a[i][2]-a[i][0]+a[i-1][0]});
        pr[i]=pr[i-1]+a[i][2]-a[i][0]+a[i-1][0];
    }
    for(int i=0;i<n;i++){
        int l=i,r=N-1;
        while(l<r){
            int m=(l+r+1)/2;
            if(query(1,0,N-1,m,r).S+(m?pr[m-1]:0)-pr[i]+a[i][2]>=0)l=m;
            else r=m-1;
        }
        res=max(res,pg[l]-(i?pg[i-1]:0));
    }
    cout<<res;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52