oj.uz

Submission #86752

# Submission time Handle Problem Language Result Execution time Memory
86752 2018-11-27T09:17:27 Z duy_tran Divide and conquer (IZhO14_divide) C++14
0 / 100
 7 ms 884 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 884 KB Output isn't correct
2 Halted 0 ms 0 KB -