记录编号	249283	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	非负的部分和	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	2.781 s
提交时间	2016-04-12 14:54:37	内存使用	23.21 MiB

#include <fstream>
#include <algorithm>
#include <cstring>
#define N 1000110
using namespace std;
ifstream in("sumc.in");
ofstream out("sumc.out");
int sum[N]={0},s[N]={0};
int n,minum;
int INF=2147483636-100000;
class rangetree
{
public:
	int minv[4*N];
	void clear()
	{
		int i;
		for(i=1;i<=4*n;i++)
		{
			minv[i]=INF;
		}
	}
	void pushup(int o)
	{
		minv[o]=min(minv[o<<1],minv[o<<1|1]);
	}
	void modify(int o,int l,int r,int x,int v)
	{
		if(l==r)minv[o]=v;
		else
		{
			int mid=(l+r)>>1;
			if(x<=mid)modify(o<<1,l,mid,x,v);
			else modify(o<<1|1,mid+1,r,x,v);
			pushup(o);
		}
	}
	int query(int o,int l,int r,int ql,int qr)
	{
		if(r<ql||l>qr)return INF;
		int mid=(l+r)>>1;
		if(ql<=l&&r<=qr)return minv[o];
		int ans=INF;
		ans=min(ans,query(o<<1,l,mid,ql,qr));
	    ans=min(ans,query(o<<1|1,mid+1,r,ql,qr));
		return ans;
	}
}A;
void read()
{
	int i;
	in>>n;
	minum=INF;
	for(i=1;i<=n;i++)
	{
		in>>s[i];
		sum[i]=sum[i-1]+s[i];
	}
	//out<<minum<<endl;
}
void work()
{
	int i,L,R,ans=0;
	
	A.clear();
	//A.modify(1,1,n,0,INF);
	for(i=1;i<=n;i++)A.modify(1,1,n,i,sum[i]);
	/*for(i=1;i<=n;i++)
	{
		out<<sum[i]<<' ';
	}
	out<<endl;*/
	for(i=1;i<=n;i++)
	{
	    L=A.query(1,1,n,i,n)-sum[i-1];
		//out<<L<<endl;
		if(i>1)R=A.query(1,1,n,1,i-1)+sum[n]-sum[i-1];
		else R=INF;
		//out<<L<<' '<<R<<endl;
		if(L>=0&&R>=0)ans++;
	}
	out<<ans<<endl;
	//for(i=1;i<=n;i++)out<<A.query(1,1,n,i,i)<<endl;
}
int main()
{
	//out<<INF<<endl;
	read();
	work();
	return 0;
}