配点 : $400$ 点

問題文

長さ $N$ の正整数列 $A=a_1,a_2, \cdots ,a_{N}$ と整数 $K$ が与えられます。$A$ の連続する部分列であって、以下の条件を満たすようなものは何個あるでしょうか。

• (条件) 連続部分列に含まれる全ての要素の値の和は、$K$ 以上である。

ただし、ある二つの連続部分列が列として同じでも、取り出された位置が異なるならそれらは別々に数えるものとします。

出力が $32bit$ 整数型に収まらない場合があることに注意してください。

制約

• $1 \leqq a_i \leqq 10^5$
• $1 \leqq N \leqq 10^5$
• $1 \leqq K \leqq 10^{10}$

入力

入力は以下の形式で標準入力から与えられます。

$N$ $K$

$a_1$ $a_2$ $...$ $a_N$

出力

条件を満たすような連続部分列の個数を出力してください。

4 10
6 1 2 7

2

• $A[1..4]=a_1,a_2,a_3,a_4$ (要素の値の和は $16$)
• $A[2..4]=a_2,a_3,a_4$ (要素の値の和は $10$)

の二通りです。

3 5
3 3 3

3

ある二つの連続部分列が列として同じでも、取り出された位置が異なるならそれらは別々に数えることに注意してください。

10 53462
103 35322 232 342 21099 90000 18843 9010 35221 19352

36