제출 #861715

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
861715		Dec0Dedd	Bigger segments (IZhO19_segments)	C++14	100 / 100	214 ms	102992 KiB

segments

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const int N = 5e5+10;
const int K = 20;
const ll INF = 1e18;

ll a[N], p[N], x[N], lg[N], st[K][N], dp[N], n;

ll que(int l, int r) {
    int i=lg[l-r+1];
    return min(st[i][l], st[i][r+(1<<i)-1]);
}

int main() {
    cin>>n;
    for (int i=1; i<=n; ++i) cin>>a[i], p[i]=p[i-1]+a[i];

    lg[1]=0;
    for (int i=2; i<N; ++i) lg[i]=lg[i/2]+1;

    for (int i=1; i<=n; ++i) {
        for (int j=0; j<K; ++j) st[j][i]=INF;
    }

    for (int j=1; j<K; ++j) st[j][1]=0;
    st[0][1]=2*p[1], dp[1]=1, x[1]=2*p[1];
    for (int i=2; i<=n; ++i) {
        int l=1, r=i-1, res=0;
        while (l <= r) {
            int m=(l+r)/2;
            if (que(i-1, m) <= p[i]) l=m+1, res=m;
            else r=m-1;
        } x[i]=p[i]-p[res]+p[i];
        dp[i]=dp[res]+1;

        st[0][i]=x[i];
        for (int j=1; j<K; ++j) {
            st[j][i]=min(st[j-1][i], i-(1<<(j-1)) >= 0 ? st[j-1][i-(1<<(j-1))] : 0);
        }
    }

    cout<<dp[n]<<"\n";
}

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