Submission #86751

#	Time	Username	Problem	Language	Result	Execution time	Memory
86751		duy_tran	금 캐기 (IZhO14_divide)	C++14	0 / 100	224 ms	7004 KiB

divide

#include<bits/stdc++.h>
using namespace std;

const int maxn=(int)1e5+50;
int n,x[maxn];
long long gold[maxn],energy[maxn],Max;
vector<long long> gt;
int minn[4*maxn],L[4*maxn],R[4*maxn],leaf[maxn];

void BuildTree(int id,int l,int r)
{
    L[id]=l;
    R[id]=r;

    if(l==r)
    {
        minn[id]=(int)1e6;
        leaf[l]=id;
        return;
    }

    int mid=(l+r)/2;

    BuildTree(id*2,l,mid);
    BuildTree(id*2+1,mid+1,r);
}

void Up(int id,int gt)
{
    minn[id]=gt;
    id/=2;

    while(id>0)
    {
        minn[id]=min(minn[id*2],minn[id*2+1]);
        id/=2;
    }
}

int Get(int id,int v)
{
    if(L[id]>v)return (int)1e6;

    if(R[id]<=v)return minn[id];

    return min(Get(id*2,v),Get(id*2+1,v));
}

int main()
{
    cin>>n;

    gt.push_back(0);

    Max=0;

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

        Max=max(Max,g);

        gold[i]=gold[i-1]+g;
        energy[i]=energy[i-1]+d;

        //cout<<energy[i]<<" "<<x[i]<<" "<<energy[i]-x[i]<<'\n';

        gt.push_back(energy[i]-x[i]);
    }

    sort(gt.begin(),gt.end());

    unique(gt.begin(),gt.end());

    BuildTree(1,0,n);

    int pos=lower_bound(gt.begin(),gt.end(),0)-gt.begin();

    Up(leaf[pos],0);

    for(int i=1;i<=n;++i)
    {
        long long p=energy[i]-x[i];

        auto t=lower_bound(gt.begin(),gt.end(),p);

        int pos=t-gt.begin();

        if(pos==0)continue;

        int r=Get(1,pos);

        if(r!=(int)1e6)Max=max(Max,gold[i]-gold[r-1]);

        Up(leaf[pos],i);
    }

    cout<<Max;
}

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