记录编号	551279	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2228.非负的部分和	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	2.349 s
提交时间	2020-05-15 11:01:58	内存使用	59.43 MiB

#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;
}