← 返回题目列表

AtCoder · awc0100_f

F. 连续间隔的销售目标

中文机器翻译题面 查看原题

分数: 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