Submission #199425

#	Time	Username	Problem	Language	Result	Execution time	Memory
199425		semiauto	Bigger segments (IZhO19_segments)	C++14	100 / 100	145 ms	18936 KiB

segments

#include <bits/stdc++.h>
using namespace std;
long long sum[500002];
int dp[500002];
pair <long long,int> hey[500002];
int main() {
    int n;
    scanf("%d",&n);
    int s=1;
    for (int i=1;i<=n;i++) {
        int x;
        scanf("%d",&x);
        sum[i]=sum[i-1]+x;
        int pos=1;
        for (int j=18;j>=0;j--)
            if (pos+(1<<j)<=s && hey[pos+(1<<j)].first<=sum[i])
                pos+=(1<<j);
        dp[i]=dp[hey[pos].second]+1;
        for (;s>=0;s--)
            if (hey[s].first<2*sum[i]-sum[hey[pos].second])
                break;
        hey[++s]={2*sum[i]-sum[hey[pos].second],i};
    }
    printf("%d\n",dp[n]);
}

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:8:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
segments.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~

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