TopCoderOpen 2018 Round3A Medium ProductThreshold

しょうもないミス。
http://community.topcoder.com/stat?c=problem_statement&pm=14949

問題

N要素の整数列A[i]が与えられる。これは負の値やゼロも含みうる。
この整数列の空でない連続部分列において、要素の積がLimit以下になるものは何通りか。

解法

ゼロは厄介なので、まず部分列にゼロを含むケースは先に数え上げてしまおう。
後はゼロを含まないAの部分列において、さらにその部分列を考えることにする。

部分列の左端Lを決めたとき、右端が満たすべき条件はどうなるかを考える。
まず積の絶対値がLimit以下となる最長の位置Rを求めよう。
これは尺取り法でもよいし、自分は下記の通り「次の絶対値が２以上の値を探す」という処理を繰り返した。
Codeforces #489 Div2 D. Nastya and a Game - kmjp's blog

右端がR以下の場合、明らかに題意を満たす。
Rより大きい場合、積の符号が負なら題意を満たす。
よって、累積和の要領で積の符号が正・負となるような右端を先に数え上げておくとよい。

class ProductThreshold {
	public:
	ll L;
	vector<ll> A,B;
	
	ll hoge() {
		vector<int> C[3];
		int i;
		int N=B.size();
		C[0].push_back(0);
		C[1].push_back(0);
		C[2].push_back(0);
		int cur=0;
		FOR(i,N) {
			if(B[i]<0) cur^=1;
			C[2].push_back(cur);
			C[0].push_back(C[0].back()+(cur==0));
			C[1].push_back(C[1].back()+(cur==1));
		}
		vector<int> nex(N+1);
		nex[N]=N;
		int ne=N;
		for(i=N-1;i>=0;i--) {
			nex[i]=ne;
			if(abs(B[i])>1) ne=i;
		}
		
		ll ret=0;
		FOR(i,N) {
			ll cur=B[i];
			int R=i;
			while(abs(cur)<=L && R<N) {
				R=nex[R];
				if(R==N) break;
				cur*=B[R];
			}
			ret+=R-i;
			int cb=C[2][i]^1;
			ret+=C[cb].back()-C[cb][R];
		}
		return ret;
		
		
	}
	
	long long subarrayCount(int N, int limit, vector <int> Aprefix, int spread, int offset) {
		L=limit;
		A.clear();
		FORR(a,Aprefix) A.push_back(a);
		ll seed = abs(A.back());
		int i;
		for(i=Aprefix.size();i<N;i++) {
			seed = (seed*1103515245LL + 12345) % (1LL<<31);
			A.push_back(seed%spread+offset);
		}
		
		ll ret=0;
		int pre=-1;
		B.clear();
		FOR(i,N) {
			if(A[i]==0) {
				ret+=1LL*(i-pre)*(N-i);
				ret += hoge();
				B.clear();
				pre=i;
			}
			else {
				B.push_back(A[i]);
			}
		}
		ret+=hoge();
		
		
		return ret;
		
	}
}

まとめ

上記CFの問題が頭に浮かんだのであまり苦労しなかったのだけど、Aの生成にabsを取り忘れて落ちた…。