比赛 20160412 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 非负的部分和 最终得分 100
用户昵称 mikumikumi 运行时间 4.443 s
代码语言 C++ 内存使用 49.91 MiB
提交时间 2016-04-12 11:15:26
显示代码纯文本
#include<cstdio>
#include<iostream>
using namespace std;
const int SIZEN=1000100,INF=0x7fffffff/2;
int N;
int s[SIZEN];
class miku
{
public:
	int l,r;
	int sum;
}tr[SIZEN*4];
void built(int root,int l,int r)
{
	tr[root].l=l;tr[root].r=r;
	if(l==r)
	{
		tr[root].sum=s[l];
		return;
	}
	int mid=(l+r)/2;
	built(root*2,l,mid);built(root*2+1,mid+1,r);
	tr[root].sum=min(tr[root*2].sum,tr[root*2+1].sum);
}
void read()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
		scanf("%d",&s[i]);
	s[0]=0;
	for(int i=1;i<=N;i++) s[i]+=s[i-1];
}
int query(int root,int l,int r)
{
	//cout<<l<<" "<<r<<endl;
	if(r<tr[root].l||l>tr[root].r) return INF;
	if(l<=tr[root].l&&tr[root].r<=r) return tr[root].sum;
	int mid=(l+r)/2;
	int re=min(query(root*2,l,r),query(root*2+1,l,r));
	return re;
}
void work()
{
	built(1,1,N);
	int ans=0;
	int tem=query(1,1,1);
	//cout<<tem<<endl;
	for(int i=1;i<=N;i++)
	{
		int tem1=query(1,i,N)-s[i-1];
		int tem2=query(1,1,i-1)+s[N]-s[i-1];
		//cout<<tem1<<" "<<tem2<<endl;
		if(tem1>=0&&tem2>=0) ans++;
	}
	printf("%d\n",ans);
}
int main()
{
	freopen("sumc.in","r",stdin);
	freopen("sumc.out","w",stdout);
	read();
	work();
	return 0;
}