Submission #842149

#	Time	Username	Problem	Language	Result	Execution time	Memory
842149		hentai_lover	Bigger segments (IZhO19_segments)	C++14	37 / 100	178 ms	262144 KiB

segments

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

typedef long long ll;

const long long oo = 1LL * 1e15;

struct kek{
    int l = -1;
    int r = -1;
    pair<int, int> ans;
} emp;

struct ST{
    vector<kek> t;
    void uni(){
        t.push_back(emp);
    }

    void upd(ll poz, pair<int,int> val, int v = 0, ll l = 0, ll r = oo){
        if(poz < 0)return;
        if(l == r){t[v].ans = max(t[v].ans, val);return;}

        ll c = (l + r)>>1;

        if(t[v].l < 0){t[v].l = t.size(); t.push_back(emp);}
        if(t[v].r < 0){t[v].r = t.size(); t.push_back(emp);}

        if(poz <= c)upd(poz, val, t[v].l, l, c);
        else upd(poz, val, t[v].r, c + 1, r);

        t[v].ans = max(t[t[v].l].ans, t[t[v].r].ans);
    }

    pair<int, int> get(ll l, ll r, int v = 0, ll tl = 0, ll tr = oo){
        if(l > r)return {-228, -228};
        if(tl == l && tr == r)return t[v].ans;

        ll c = (tl + tr) >> 1;

        if(t[v].l < 0){t[v].l = t.size(); t.push_back(emp);}
        if(t[v].r < 0){t[v].r = t.size(); t.push_back(emp);}

        return max(get(l, min(r, c), t[v].l, tl, c), get(max(l, c + 1), r, t[v].r, c + 1, tr));
    }
};

int32_t main() {
    ios_base::sync_with_stdio(0);
    //cout<<oo<<endl;

    int n;
    cin>>n;
    int a[n];
    for(int i = 0; i < n; i += 1)cin>>a[i];

    ll sf[n + 1] = {};
    for(int i = n - 1; i >= 0; i -= 1)sf[i] = sf[i + 1] + a[i];

    ///dp[p] = {ans, min_sum}
    pair<int,ll> dp[n];
    ll sum = 0;
    for(int i = 0; i < n; i += 1){
        sum += a[i];
        dp[i] = {1, sum};
    }

    ST tree;
    tree.uni();
    tree.upd(sf[1] - dp[0].second, {1, 0});

    for(int i = 1; i < n; i += 1){
        pair<int,int>temp = tree.get(sf[i + 1], oo);
        //cerr<<"i = "<<i<<" temp: "<<temp.first<<" "<<temp.second<<endl;
        dp[i] = max(dp[i], {temp.first + 1, sf[temp.second + 1] - sf[i + 1]});
        tree.upd(sf[i + 1] - dp[i].second, {dp[i].first, i});
    }

//    cout<<"dp:";
//    for(int i = 0; i < n; i += 1)cout<<dp[i].first<<' '<<dp[i].second<<endl;

    int ans = 0;
    for(int i = 0; i < n; i += 1){
        ans = max(ans, dp[i].first);
    }
    cout<<ans;
}
/*
5
6 2 3 9 13
*/

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27