Submission #869205

#	Time	Username	Problem	Language	Result	Execution time	Memory
869205		sleepntsheep	Bigger segments (IZhO19_segments)	C11	100 / 100	108 ms	10328 KiB

segments

#include <stdio.h>
#define N 500001

#pragma GCC target("avx2")
#pragma GCC optimize("O3,unroll-loops")

i,j,n,dp[N];
long long a[N], fw[N],x,c,p;
u(p) { for (;p<N;p+=p&-p) fw[p]-=(fw[p]-x)*(x<fw[p]); }
//long long q(p) { long long z=1e18;for(;p;p-=p&-p)z-=(z-fw[p])*(z>fw[p]); return z;}
s(){
    c=0,p=1e18;
    for(int j=(1<<19);j;j>>=1)if(c+j<=n&&(fw[j+c]<p?fw[j+c]:p)>x)c+=j,p=(fw[c]<p?fw[c]:p);
    return c+1;
}
main()
{
    scanf("%d",&n);for(;++i<N;fw[i]=1e18);
    for (i=1;i<=n;++i) scanf("%lld",a+i),x=a[i]+=a[i-1],dp[i]=1+dp[j=n+1-s(),j>0?j:(j=0)],x=2*a[i]-a[j],u(n-i+1);
    printf("%d",dp[n]);
    return 0;
}

Compilation message (stderr)

segments.c:7:1: warning: data definition has no type or storage class
    7 | i,j,n,dp[N];
      | ^
segments.c:7:1: warning: type defaults to 'int' in declaration of 'i' [-Wimplicit-int]
segments.c:7:3: warning: type defaults to 'int' in declaration of 'j' [-Wimplicit-int]
    7 | i,j,n,dp[N];
      |   ^
segments.c:7:5: warning: type defaults to 'int' in declaration of 'n' [-Wimplicit-int]
    7 | i,j,n,dp[N];
      |     ^
segments.c:7:7: warning: type defaults to 'int' in declaration of 'dp' [-Wimplicit-int]
    7 | i,j,n,dp[N];
      |       ^~
segments.c:9:1: warning: return type defaults to 'int' [-Wimplicit-int]
    9 | u(p) { for (;p<N;p+=p&-p) fw[p]-=(fw[p]-x)*(x<fw[p]); }
      | ^
segments.c: In function 'u':
segments.c:9:1: warning: type of 'p' defaults to 'int' [-Wimplicit-int]
segments.c: At top level:
segments.c:11:1: warning: return type defaults to 'int' [-Wimplicit-int]
   11 | s(){
      | ^
segments.c:16:1: warning: return type defaults to 'int' [-Wimplicit-int]
   16 | main()
      | ^~~~
segments.c: In function 'u':
segments.c:9:55: warning: control reaches end of non-void function [-Wreturn-type]
    9 | u(p) { for (;p<N;p+=p&-p) fw[p]-=(fw[p]-x)*(x<fw[p]); }
      |                                                       ^
segments.c: In function 'main':
segments.c:18:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%d",&n);for(;++i<N;fw[i]=1e18);
      |     ^~~~~~~~~~~~~~
segments.c:19:24: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     for (i=1;i<=n;++i) scanf("%lld",a+i),x=a[i]+=a[i-1],dp[i]=1+dp[j=n+1-s(),j>0?j:(j=0)],x=2*a[i]-a[j],u(n-i+1);
      |                        ^~~~~~~~~~~~~~~~~

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