Submission #844998

#	Time	Username	Problem	Language	Result	Execution time	Memory
844998		hentai_lover	Bigger segments (IZhO19_segments)	C++14	100 / 100	118 ms	30656 KiB

segments

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

typedef long long ll;

const long long oo = 1LL * 1e15;
const int N = 5e5;
int n;
struct ST{
    vector<long long> t;
    void uni(){
        t.resize(N * 3);
        for(auto &i:t)i = -oo;
    }

    void upd(int poz, ll val, int v = 1, int l = 0, int r = n - 1){
        if(poz < 0)return;
        if(l == r){t[v] = val;return;}

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

        if(poz <= c)upd(poz, val, v<<1, l, c);
        else upd(poz, val, (v<<1)|1, c+1, r);

        t[v] = max(t[v<<1], t[(v<<1)|1]);
    }

    int get(long long val, int v = 1, int l = 0, int r = n - 1){
        if(l == r)return l;
        int c = (l + r) >> 1;

        if(t[(v<<1)|1]>=val)return get(val, (v<<1)|1,c+1,r);
        return get(val, v<<1,l,c);
    }
};

int32_t main() {
    ios_base::sync_with_stdio(0);
    //cout<<oo<<endl;
    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(0, sf[1] - dp[0].second);
    //cerr<<"upd: "<<sf[1] - dp[0].second<<endl;

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

    }

//    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: 36 / 36
• Subtask 5: 27 / 27