#ABC130D. 足够的数组
足够的数组
AT_abc130_d [ABC130D] Enough Array
题目描述
给定一个长度为 的正整数序列 和一个整数 。请你求出有多少个满足以下条件的连续子数组:
该连续子数组中所有元素的和不小于 。
注意,即使两个连续子数组的内容相同,只要它们在序列中的位置不同,也要分别计数。
【名词解释】
子数组:子数组为从原数组中,连续的选择一段元素(可以全选、可以不选)得到的新数组。
输入格式
第一行输入两个整数 $n,k \left(1 \leqq n \leqq 10^5;\ 1 \leqq k \leqq 10^{10}\right)$ 代表序列的长度和阈值。
第二行输入 个整数 $a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq 10^5\right)$ 代表序列中的元素。
输出格式
在一行上输出一个整数,代表满足条件的连续子数组数量。
请注意,答案可能超出 位整数范围。
测试样例
4 10
6 1 2 7
2
样例 1 解释
在这个样例中,满足条件的连续子数组有:
,元素和为 ;
,元素和为 。
共 种,因此输出 。
3 5
3 3 3
3
样例 2 解释
在这个样例中,满足条件的连续子数组为 、 与 ,共 种。
其中 与 的内容相同,但它们的位置不同,需要分别计数。
10 53462
103 35322 232 342 21099 90000 18843 9010 35221 19352
36