Submission #863036

#	Time	Username	Problem	Language	Result	Execution time	Memory
863036		Hosen_ba	Bigger segments (IZhO19_segments)	C++17	100 / 100	248 ms	24892 KiB

segments

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5;
ll st[4*N+2];
const ll inf=1e18;
void build(int node,int l,int r){
    st[node]=inf;
    if(l==r)
        return;
    int mid=(l+r)/2;
    build(2*node,l,mid);
    build(2*node+1,mid+1,r);
}
void upd(int node,int l,int r,int idx,ll val){
    if(l==r){
        st[node]=val;
        return;
    }
    int mid=(l+r)/2;
    if(idx<=mid){
        upd(2*node,l,mid,idx,val);
    }else{
        upd(2*node+1,mid+1,r,idx,val);
    }
    st[node]=min(st[2*node],st[2*node+1]);
}
int findd(int node,int l,int r,ll val){
    if(l==r){
        return l;
    }
    int mid=(l+r)/2;
    if(st[2*node+1]<=val){
        return findd(2*node+1,mid+1,r,val);
    }else{
        return findd(2*node,l,mid,val);
    }
}
int main(){
    int n;
    cin>>n;
    ll a[n+2];
    a[0]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]+=a[i-1];
    }
    build(1,0,n);
    upd(1,0,n,0,0);
    pair<int,ll>dp[n+2];
    dp[0]={0,0};
    for(int i=1;i<=n;i++){
        int k=findd(1,0,n,a[i]);
        dp[i].first=dp[k].first+1;
        dp[i].second=a[i]-a[k];
        upd(1,0,n,i,a[i]+dp[i].second);
    }
    cout<<dp[n].first<<endl;
}

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