PKU4040 Non-negative Partial Sums

こんなのsegment treeでO(n log n)で余裕だな！とやってたらずっとTLEしていて頭が悪い…
[0,a]と[b,n]のクエリしか使わないんだから線形でしょうに・・・

#include<stdio.h>
#include<algorithm>
using namespace std;
int b[1100000];
char str[5000000];
int sz;
int c[1048576];
int R[1048576];
int main(){
	int a;
	while(1){
		int at=0;
		int tmp=0;
		int nega=1;
		a=0;
		gets(str);
		for(int i=0;str[i];i++)a=a*10+str[i]-'0';
		if(a==0)return 0;
		gets(str);
		for(int i=0;at<a;i++){
			if(str[i]=='-')nega=-1;
			else if(str[i]>'9'||str[i]<'0'){
				b[at++]=nega*tmp;
				tmp=0;
				nega=1;
			}else{
				tmp=tmp*10+str[i]-'0';
			}
		}
		int now=0;
		c[0]=0;
		for(int i=0;i<a;i++){
			now+=b[i];
			c[i+1]=now;
		}
		tmp=c[a];
		for(int i=a;i>=1;i--){
			R[i]=tmp;
			tmp=min(tmp,c[i-1]);
		}
		int ret=0;
		int val=0;
		for(int i=0;i<a;i++){
			if(R[i+1]-c[i]>=0&&c[a]-c[i]+val>=0)ret++;
			val=min(val,c[i+1]);
		}
		printf("%d\n",ret);
	}
}