比赛 |
20160412 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
非负的部分和 |
最终得分 |
100 |
用户昵称 |
瑆の時間~無盡輪迴·林蔭 |
运行时间 |
3.916 s |
代码语言 |
C++ |
内存使用 |
59.43 MiB |
提交时间 |
2020-05-15 10:18:18 |
显示代码纯文本
#include<iostream>
#include<cstdio>
using namespace std;
const int N=2000010;
int n,a[N],sum[N],mi[N*4];
int ls(int x)
{
return x<<1;
}
int rs(int x)
{
return x<<1|1;
}
void pushup(int x)
{
mi[x]=min(mi[ls(x)],mi[rs(x)]);
}
void build(int x,int l,int r)
{
if(l==r)
{
mi[x]=sum[l];
return;
}
int mid=(l+r)>>1;
build(ls(x),l,mid);
build(rs(x),mid+1,r);
pushup(x);
}
int Query(int x,int l,int r,int nl,int nr)
{
if(nl<=l&&nr>=r)
{
return mi[x];
}
int ret=2147483647,mid=(l+r)>>1;
if(nl<=mid)
{
ret=min(ret,Query(ls(x),l,mid,nl,nr));
}
if(nr>mid)
{
ret=min(ret,Query(rs(x),mid+1,r,nl,nr));
}
return ret;
}
int main()
{
freopen("sumc.in","r",stdin);
freopen("sumc.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i+n]=a[i];
}
for(int i=1;i<=n*2;i++)
{
sum[i]=sum[i-1]+a[i];
}
build(1,1,n*2);
int ans=0;
for(int i=1;i<=n;i++)
{
int SD=Query(1,1,n*2,i,i+n-1);
if(SD>=sum[i-1])
ans++;
}
printf("%d",ans);
return 0;
}