比赛 20160412 评测结果 AWAWWAWAAAWAWWAWAAWW
题目名称 非负的部分和 最终得分 50
用户昵称 Satoshi 运行时间 2.335 s
代码语言 C++ 内存使用 38.46 MiB
提交时间 2016-04-12 10:02:43
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <cstring>
#define N 1000010
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;
int ans=0;
class rangetree
{
public:
	int setv[4*N];
	int minv[4*N];
	void clear()
	{
		memset(setv,0,sizeof(setv));
		memset(minv,0,sizeof(minv));
	}
	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)
	{
		int mid=(l+r)>>1;
		if(ql<=l&&r<=qr)return minv[o];
		int ans=INF;
		if(ql<=mid)ans=min(ans,query(o<<1,l,mid,ql,qr));
	    else 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;
	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++)
	{
	    L=A.query(1,1,n,i,n)-sum[i-1];
		if(i>1)R=A.query(1,1,n,1,i-1)+sum[n]-sum[i-1];
		else R=INF;
		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;
}