Submission #869128

#	Time	Username	Problem	Language	Result	Execution time	Memory
869128		12345678	Bigger segments (IZhO19_segments)	C++17	100 / 100	113 ms	31828 KiB

segments

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=5e5+5;
ll dp[nx], a[nx], qs[nx], lst[nx], n;

struct segtree
{
    ll d[4*nx];
    void update(int l, int r, int i, int idx, ll vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return void(d[i]=vl);
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=min(d[2*i], d[2*i+1]);
    }
    ll query(int l, int r, int i, ll vl)
    {
        if (l==r) return l;
        int md=(l+r)/2;
        if (d[2*i+1]<=vl) return query(md+1, r, 2*i+1, vl);
        else return query(l, md, 2*i, vl);
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>a[i], qs[i]=qs[i-1]+a[i];
    for (int i=1; i<=4*n; i++) s.d[i]=1e18;
    s.update(0, n, 1, 0, 0);
    for (int i=1; i<=n; i++)
    {
        ll l=s.query(0, n, 1, qs[i]);
        dp[i]=dp[l]+1;
        lst[i]=qs[i]-qs[l];
        //cout<<i<<' '<<l<<' '<<dp[i]<<' '<<lst[i]<<'\n';
        s.update(0, n, 1, i, lst[i]+qs[i]);
    }
    cout<<dp[n];
}

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