← 返回题目列表

AtCoder · awc0049_c

C. 间隔总和

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

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