Submission #1153259

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153259		asdasd	Bigger segments (IZhO19_segments)	C++20	73 / 100	1595 ms	23324 KiB

segments

//gm  --- akezhon
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define tm (tl+tr)/2
#define TL v+v, tl, tm
#define TR v+v+1, tm+1, tr
#define DA l <= tl && tr <= r
#define NE r < tl || tr < l
#define int long long
using namespace std;

const int N=5e5+7;
const int mod=998244353;
const int inf=2e18;

int dp[N];
int sm[N];
int a[N];
int p[N];
int n;
int t[N*4];
int L[N];

void upd(int pos, int val, int v=1, int tl=1, int tr=n){
    if(tl == tr){
        t[v]=val;
        return;
    }
    if(pos <= tm)upd(pos, val, TL);
    else upd(pos, val, TR);
    t[v]=min(t[v+v],t[v+v+1]);
}
int get(int l, int r, int v=1, int tl=1, int tr=n){
    if(DA)return t[v];
    if(NE)return inf;
    return min(get(l, r, TL), get(l, r, TR));
}
void AlemAmenov(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        p[i] = p[i-1] + a[i];
        sm[i]=inf;
    }
    for(int i=1; i <= n; i++){
        dp[i] = dp[i-1];
        sm[i] = sm[i-1]+a[i];
        int l = L[dp[i]], r=i-1, pos=-1;
        while(l <= r){
            int m = (l+r)/2;
            if(get(m, i-1) <= p[i])l=m+1, pos=m;
            else r=m-1; 
        }
        if(pos != -1){
            dp[i] = dp[pos]+1;
            sm[i] = p[i]-p[pos];
        }
        else if(dp[i] > 0){
            l = L[dp[i]-1], r=L[dp[i]]-1;
            while(l <= r){
                int m = (l+r)/2;
                if(get(m, L[dp[i]]-1) <= p[i])l=m+1, pos=m;
                else r=m-1;
            }
            if(pos != -1 && p[i]-p[pos] < sm[i]){
                sm[i] = p[i]-p[pos];
            }
        }
        if(L[dp[i]] == 0)L[dp[i]]=i;
        upd(i, sm[i]+p[i]);
    }
    cout << dp[n]+1;
}
signed main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int RealName=1;
    // cin >> RealName;
    // srand(time(0));

    while(RealName--)
        AlemAmenov();
    
return 0;
}

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