分数: 366 分
问题陈述
高桥正在分析销售数据 N 购物区的商店。购物区的商店编号为 1 to N,以及各店铺每天的销售额 i is V_i 日元。
购物区正在计划开展一项活动,将邻近的商店指定为“促销区”。促销区域是通过选择一对整数来定义的 (l, r) (1 \leq l \leq r \leq N)并包括编号中的所有连续商店 l 至号码 r。不同对 (l, r) 被视为不同的区域。
但是,为了确保足够的活动效果,仅限所选商店总销售额至少为 将采用 K 日元。也就是说,条件 必须满足 V_l + V_{l+1} + \cdots + V_r \geq K 。
高桥想知道可以采用多少个可能的促销区域。找出对的数量 (l, r) 满足条件。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{14}
- 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
- 所有输入值均为整数
输入
N K V_1 V_2 \ldots V_N
- 第一行包含一个整数 N 代表商店数量和一个整数 K 代表最低要求的总销售额,以空格分隔。
- 第二行包含整数 V_1, V_2, \ldots, V_N 代表每个商店的销售额,以空格分隔。
输出
一行打印满足条件的促销区域的数量,即对的数量 (l, r) (1 \leq l \leq r \leq N)这样 V_l + V_{l+1} + \cdots + V_r \geq K。保证答案在 64 位整数范围内。
示例输入 1
5 10 3 1 4 1 5
示例输出 1
3
示例输入 2
8 15 5 3 8 2 7 4 6 1
示例输出 2
18
示例输入 3
10 1000000000000 100000000 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 1000000000
示例输出 3
0