oj.uz

Submission #86765

# Submission time Handle Problem Language Result Execution time Memory
86765 2018-11-27T09:53:52 Z duy_tran Divide and conquer (IZhO14_divide) C++14
100 / 100
 172 ms 5212 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn=(int)2e5+50;
int n,x[maxn],bit[maxn];
long long gold[maxn],energy[maxn],Max;
vector<long long> gt;

void Up(int id,int gt)
{
     for(;id<=2*n+2;id+=id&-id)bit[id]=min(bit[id],gt);
}

int Get(int id)
{
    int res=(int)1e6;

    for(;id>0;id-=id&-id)res=min(res,bit[id]);

    return res;
}

int main()
{
    cin>>n;

    memset(bit,(int)1e6,sizeof(bit));

    Max=0;

    for(int i=1;i<=n;++i)
    {
        cin>>x[i]>>gold[i]>>energy[i];

        Max=max(Max,gold[i]);

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

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

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

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

    for(int i=1;i<=n;++i)
    {
        int pos=lower_bound(gt.begin(),gt.end(),energy[i]-x[i])-gt.begin()+1;

        int l=Get(pos);

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

        pos=lower_bound(gt.begin(),gt.end(),energy[i-1]-x[i])-gt.begin()+1;

        Up(pos,i);
    }

    cout<<Max;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 3 ms 1148 KB Output is correct
3 Correct 2 ms 1320 KB Output is correct
4 Correct 3 ms 1320 KB Output is correct
5 Correct 3 ms 1320 KB Output is correct
6 Correct 3 ms 1320 KB Output is correct
7 Correct 3 ms 1320 KB Output is correct
8 Correct 3 ms 1360 KB Output is correct
9 Correct 3 ms 1488 KB Output is correct
10 Correct 3 ms 1488 KB Output is correct
11 Correct 3 ms 1504 KB Output is correct
12 Correct 2 ms 1504 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1504 KB Output is correct
2 Correct 3 ms 1504 KB Output is correct
3 Correct 3 ms 1504 KB Output is correct
4 Correct 3 ms 1504 KB Output is correct
5 Correct 4 ms 1504 KB Output is correct
6 Correct 4 ms 1504 KB Output is correct
7 Correct 4 ms 1504 KB Output is correct
8 Correct 4 ms 1504 KB Output is correct
9 Correct 5 ms 1504 KB Output is correct
10 Correct 5 ms 1504 KB Output is correct
11 Correct 9 ms 1660 KB Output is correct
12 Correct 10 ms 1660 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1660 KB Output is correct
2 Correct 13 ms 1916 KB Output is correct
3 Correct 16 ms 1916 KB Output is correct
4 Correct 71 ms 3204 KB Output is correct
5 Correct 81 ms 3308 KB Output is correct
6 Correct 172 ms 5212 KB Output is correct
7 Correct 134 ms 5212 KB Output is correct
8 Correct 137 ms 5212 KB Output is correct
9 Correct 135 ms 5212 KB Output is correct
10 Correct 131 ms 5212 KB Output is correct
11 Correct 154 ms 5212 KB Output is correct
12 Correct 159 ms 5212 KB Output is correct