AT_abc130_d [ABC130D] Enough Array

题目描述

给定一个长度为 $N$ 的正整数序列 $A=a_1,a_2,\dots,a_N$ 和一个整数 $K$。请问有多少个满足以下条件的连续子序列：

• （条件）该连续子序列中所有元素的和不小于 $K$。

注意，即使两个连续子序列的内容相同，只要它们在序列中的位置不同，也要分别计数。

请注意，输出结果可能超出 $32$ 位整数范围。

输入格式

输入以以下格式从标准输入中给出：

$N$ $K$ $a_1$ $a_2$ $\dots$ $a_N$

输出格式

输出满足条件的连续子序列的个数。

样例 1

输入

4 10
6 1 2 7

输出

2

样例 2

输入

3 5
3 3 3

输出

3

样例 3

输入

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

输出

36

说明/提示

限制条件

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

样例解释 1

• $A[1..4]=a_1,a_2,a_3,a_4$（元素和为 $16$）
• $A[2..4]=a_2,a_3,a_4$（元素和为 $10$）

共两种情况。

样例解释 2

请注意，即使两个连续子序列的内容相同，只要它们在序列中的位置不同，也要分别计数。

由 ChatGPT 4.1 翻译