oj.uz

답안 #86750

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
86750 2018-11-27T09:11:39 Z duy_tran 금 캐기 (IZhO14_divide) C++14
0 / 100
 227 ms 7080 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn=(int)1e5+50;
int n,x[maxn];
long long gold[maxn],energy[maxn];
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);

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

        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);

    long long Max=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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 3 ms 588 KB Output is correct
3 Incorrect 3 ms 588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 1044 KB Output is correct
2 Correct 16 ms 1300 KB Output is correct
3 Correct 26 ms 1388 KB Output is correct
4 Correct 88 ms 3792 KB Output is correct
5 Correct 92 ms 3800 KB Output is correct
6 Correct 227 ms 7080 KB Output is correct
7 Correct 145 ms 7080 KB Output is correct
8 Correct 151 ms 7080 KB Output is correct
9 Correct 137 ms 7080 KB Output is correct
10 Incorrect 141 ms 7080 KB Output isn't correct
11 Halted 0 ms 0 KB -