F - Median of subsequence 1
Assam
2
s
1024
MB
500
点
問題文
長さ $M$ の数列 $B$ の中央値を、 $B$ を昇順ソートした数列における $\left\lfloor\frac{M+1}{2}\right\rfloor$ 番目の値とします。例えば、 $(3,1,4)$ の中央値は $3$ 、 $(2,7,1,8)$ の中央値は $2$ 、 $(1)$ の中央値は $1$ です。
長さ $N$ の正整数列 $A=(A_1,A_2,\ldots,A_N)$ と正整数 $X$ が与えられます。 $A$ の空でない連続する部分列であって、中央値がちょうど $X$ になるものの数を求めてください。ただし、ある 2 つの部分列が列として同じでも、取り出した位置が異なるならば、それらは別々に数えるものとします。
制約
- $1\leq N\leq 2\times10^5$
- $1\leq X\leq N$
- $1\leq A_i\leq N\ \ (1\leq i\leq N)$
- 入力される値はすべて整数
部分点
入力
入力は以下の形式で標準入力から与えられる。
$N$ $X$
$A_1$ $A_2$ $\ldots$ $A_N$
出力
答えを出力せよ。
入力例 1
5 3
3 1 4 1 5
出力例 1
3
$(A_1),(A_1,A_2,A_3),(A_1,A_2,A_3,A_4,A_5)$ の $3$ 通りの部分列が条件を満たします。
例えば、$(A_1,A_2,A_3)=(3,1,4)$ は長さ $3$ の数列であり、昇順ソートすると $(1,3,4)$です。
その $\lfloor\frac{3+1}{2}\rfloor$ 番目の値は $3$ なので条件を満たしている部分列です。
入力例 2
4 4
1 1 2 3
出力例 2
0
全ての連続部分列が条件を満たしません。
入力例 3
10 1
1 1 1 1 1 1 1 1 1 1
出力例 3
55
空でない全ての連続部分列が条件を満たします。