Submission #441573

#	Time	Username	Problem	Language	Result	Execution time	Memory
441573		leaked	Bigger segments (IZhO19_segments)	C++14	100 / 100	139 ms	46240 KiB

segments

#include <bits/stdc++.h>

#define vec vector
#define sz(x) (int)x.size()
#define m_p make_pair
#define f first
#define s second
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
auto rng=bind(uniform_int_distribution<int>(1,1e9),mt19937(time(0)));
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const int N=5e5+1;
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    vec<int>a(n);
    vec<ll>pref(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        pref[i]=(i?pref[i-1]:0)+a[i];
    }
    vec<pil>dp(n,m_p(0,-2*n));
    /// pref[i]-pref[j]>=dp[j].s->pref[i]>=pref[j]+dp[j].f
    vec<vec<pii>>add(n+1,vec<pii>());
    pii mx={-2e9,-1};
    auto get=[&](int l,int r){
        return pref[r]-(l?pref[l-1]:0);
    };
    int ans=0;
    for(int i=0;i<n;i++){
        for(auto &z : add[i]) umax(mx,z);
        pii w=max(mx,m_p(0,0));
        w.f++;
//        cerr<<dp[i].f<<'
        dp[i]=m_p(w.f,get(w.s,i));
//        cerr<<dp[i].f<<' '<<dp[i].s<<endl;
        int l=i+1,r=n;
        while(l<r){
            int tm=(l+r)>>1;
            if(pref[tm]>=dp[i].s+pref[i]){
                r=tm;
            }
            else{
                l=tm+1;
            }
        }
        add[l].pb(m_p(dp[i].f,i+1));
        umax(ans,dp[i].f);
    }
    cout<<ans;
    return 0;
}

/*
10
2 1 2 2 1 1 3 2 5 5
*/

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