分数: 366 分
问题陈述
高桥有一系列 N 正整数。的 i- 第一个元素 (1 \leq i \leq N) 该序列是 A_i.
Takahashi 对该序列的连续子数组的总和感兴趣。具体来说,对于一对整数 (l, r) (1 \leq l \leq r \leq N),他考虑了来自 l-第 r-th:
A_l + A_{l+1} + \cdots + A_r
给定一个整数 K,查找对的数量 (l, r) 使得该总和最多为 K.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{14}
- 1 \leq A_i \leq 10^9
- 所有输入均为整数
输入
N K A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 表示序列中元素的数量和一个整数 K 表示总和的上限,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 表示序列的每个元素,以空格分隔。
输出
在一行上打印整数对的数量 (l, r) (1 \leq l \leq r \leq N)令人满意 A_l + A_{l+1} + \cdots + A_r \leq K.
示例输入 1
5 5 1 2 3 4 5
示例输出 1
7
示例输入 2
7 10 3 1 4 1 5 9 2
示例输出 2
15
示例输入 3
10 1000000000000 500000000 400000000 300000000 200000000 100000000 600000000 700000000 800000000 900000000 1000000000
示例输出 3
55