oj.uz

Submission #476260

# Submission time Handle Problem Language Result Execution time Memory
476260 2021-09-25T17:50:17 Z ogibogi2004 Divide and conquer (IZhO14_divide) C++14
17 / 100
 3 ms 1100 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=1e5+6;
const ll INF=2e17;
int n;
ll x[MAXN],g[MAXN],d[MAXN],pref[MAXN];
ll fen[MAXN];
vector<int>v;
void update(int idx,ll val)
{
    idx++;
    for(;idx<MAXN;idx+=idx&(-idx))
    {
        fen[idx]=max(fen[idx],val);
    }
}
ll query(int idx)
{
    idx++;
    ll ret=-INF;
    for(;idx>0;idx-=idx&(-idx))
    {
        ret=max(ret,fen[idx]);
    }
    return ret;
}
ll pref1[MAXN],output=0;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>g[i]>>d[i];
    }
    for(int i=1;i<MAXN;i++)
    {
        fen[i]=-INF;
    }
    v.push_back(0);
    for(int i=1;i<=n;i++)
    {
        pref[i]=pref[i-1]+d[i];
        pref1[i]=pref1[i-1]+g[i];
        v.push_back(pref[i]-x[i]);
        //cout<<i<<" "<<pref[i]-x[i]<<endl;
    }
    sort(v.begin(),v.end());
    for(int i=1;i<=n;i++)
    {
        //cout<<i<<":\n";
        int t=pref[i-1]-x[i];
        int l=0,r=v.size()-1,ans=-1,mid;
        while(l<=r)
        {
            mid=(l+r)/2;
            if(t<=v[mid])
            {
                r=mid-1;
            }
            else
            {
                ans=mid;
                l=mid+1;
            }
        }
        ans++;
        //cout<<ans<<endl;
        update(ans+1,-pref1[i-1]);
        l=0,r=v.size()-1,ans=-1;
        t=pref[i]-x[i];
        while(l<=r)
        {
            mid=(l+r)/2;
            if(t<=v[mid])
            {
                r=mid-1;
            }
            else
            {
                ans=mid;
                l=mid+1;
            }
        }
        ans++;
        //cout<<ans<<endl;
        output=max(output,pref1[i]+query(ans+1));
    }
    cout<<output<<endl;
return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1076 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 1 ms 1100 KB Output is correct
13 Correct 1 ms 1100 KB Output is correct
14 Correct 1 ms 1100 KB Output is correct
15 Correct 1 ms 1100 KB Output is correct
16 Correct 2 ms 1092 KB Output is correct
17 Correct 2 ms 1100 KB Output is correct
18 Incorrect 3 ms 1084 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Correct 1 ms 1100 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 1 ms 1100 KB Output is correct
6 Correct 1 ms 1100 KB Output is correct
7 Correct 1 ms 1100 KB Output is correct
8 Correct 1 ms 1076 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 1 ms 1100 KB Output is correct
13 Correct 1 ms 1100 KB Output is correct
14 Correct 1 ms 1100 KB Output is correct
15 Correct 1 ms 1100 KB Output is correct
16 Correct 2 ms 1092 KB Output is correct
17 Correct 2 ms 1100 KB Output is correct
18 Incorrect 3 ms 1084 KB Output isn't correct
19 Halted 0 ms 0 KB -