Submission #598053

#	Time	Username	Problem	Language	Result	Execution time	Memory
598053		daisy2	Divide and conquer (IZhO14_divide)	C++14	0 / 100	2 ms	3412 KiB

divide

#include<iostream>
#include<cstring>
#define endl '\n'
using namespace std;
long long n,x[100005],g[100005],e[100005],tree[400005],pr[100005],a[100005],lazy[400005],ans=0; // n<=100000
void build(long long node,long long l,long long r)
{
    if(l==r)
    {
        tree[node]=a[l];
        return;
    }
    long long mid=(l+r)/2;

    build(2*node,l,mid);
    build(2*node+1,mid+1,r);

    tree[node]=max(tree[2*node],tree[2*node+1]);
}
long long query(long long node,long long l,long long r)
{
    if(tree[node]<0) return -1;

    if(l==r)
    {
        return l;
    }

    if(lazy[node]!=0)
    {
        tree[node]+=lazy[node];
        if(l!=r)
        {
            lazy[2*node]+=lazy[node];
            lazy[2*node+1]+=lazy[node];
        }
        lazy[node]=0;
    }

    long long mid=(l+r)/2;

    long long a2=query(2*node+1,mid+1,r);
    if(a2>-1) return a2;

    return query(2*node,l,mid);
}
void update(long long node,long long l,long long r,long long le,long long ri,long long st)
{
    if(l>=le && r<=ri)
    {
        lazy[node]+=st;
    }
    if(lazy[node]!=0)
    {
        tree[node]+=lazy[node];
        if(l!=r)
        {
            lazy[2*node]+=lazy[node];
            lazy[2*node+1]+=lazy[node];
        }
        lazy[node]=0;
    }
    if(l>ri || r<le) return;
    if(l>=le && r<=ri) return;

    long long mid=(l+r)/2;
    update(2*node,l,mid,le,ri,st);
    update(2*node+1,mid+1,r,le,ri,st);

    tree[node]=max(tree[2*node],tree[2*node+1]);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;

    for(long long i=1;i<=n;i++)
    {
        cin>>x[i]>>g[i]>>e[i];

        ans=max(ans,g[i]);
        g[i]+=g[i-1];

        pr[i]=pr[i-1]+e[i];
        a[i]=pr[i]-x[i]+x[1];
    }
    memset(tree,-1,sizeof(tree));

    build(1,1,n);

    long long p;
    for(long long i=1;i<=n;i++)
    {
        p=query(1,1,n);
        if(p==-1) continue;

        ans=max(ans,g[p]-g[i-1]);

        if(i!=n)
        update(1,1,n,i+1,n,x[i+1]-x[i]-e[i]);
    }
 cout<<ans<<endl;
}

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