Codeforces #997 : Div2 D. Unique Median

Eまではすんなり。
https://codeforces.com/contest/2056/problem/D

問題

整数列Aが与えられる。各要素は[1,10]の範囲である。
この連続部分列のうち、中央値が一致するものは何通りか。なお、長さが奇数の場合中央値は常に一致すると考える。

解法

中央値が一致しないケースを除こう。
Aの部分列A'に対し中央値が一致しないのは、ある整数d以上の個数と、d未満の個数が一致する場合である。
よってdを総当たりしながら、上記個数を数え上げよう。

int T,N,A[1101010];
int C[101010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		ll ret=1LL*N*(N+1)/2;
		FOR(i,N) {
			cin>>A[i];
		}
		FOR(i,11) {
			int cur=0;
			map<int,int> M;
			C[0]=0;
			for(j=0,x=0;j<N;j++) {
				if(A[j]<=i) cur++;
				else cur--;
				C[j+1]=cur;
				if(A[j]==i) {
					while(x<=j) M[C[x++]]++;
				}
				ret-=M[cur];
			}
		}
		
		
		
		cout<<ret<<endl;
		
	}
}

まとめ

Aの値の範囲が狭いのがちょっとネタバレになっちゃってるね。