Submission #199417

#	Time	Username	Problem	Language	Result	Execution time	Memory
199417		semiauto	Bigger segments (IZhO19_segments)	C++14	73 / 100	1506 ms	16504 KiB

segments

#include <bits/stdc++.h>
using namespace std;
long long sum[500001],tree[1050000];
int dp[500001];
void update(int pos,long long val) {
    while (pos) {
        tree[pos]=min(tree[pos],val);
        pos/=2;
    }
}
long long solve(int p,int l,int r,int x,int y) {
    if (x>r || l>y)
        return 2000000000000000000ll;
    if (l>=x && r<=y)
        return tree[p];
    return min(solve(2*p,l,(l+r)/2,x,y),solve(2*p+1,(l+r)/2+1,r,x,y));
}
int main() {
    for (int i=0;i<1050000;i++)
        tree[i]=2000000000000000000ll;
    int n,N=1;
    cin>>n;
    while (N<n)
        N*=2;
    for (int i=1;i<=n;i++) {
        int x;
        cin>>x;
        sum[i]=sum[i-1]+x;
        int pos=i;
        for (int j=18;j>=0;j--)
            if (pos-(1<<j)>0 && solve(1,N,2*N-1,pos-(1<<j)+N-1,pos-1+N-1)>sum[i])
                pos-=(1<<j);
        dp[i]=dp[pos-1]+1;
        update(i+N-1,2*sum[i]-sum[pos-1]);
    }
    cout<<dp[n]<<endl;
}

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