C - Sum of Intervals Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、N 個の正の整数からなる数列を持っています。この数列の i 番目（1 \leq i \leq N）の要素は A_i です。

高橋君は、この数列の連続する区間の和に興味を持っています。具体的には、整数の組 (l, r)（1 \leq l \leq r \leq N）に対して、数列の l 番目から r 番目までの要素の和

A_l + A_{l+1} + \cdots + A_r

を考えます。

整数 K が与えられるので、この和が K 以下となるような組 (l, r) の個数を求めてください。

制約

  • 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
  • 1 行目には、数列の要素数を表す整数 N と、和の上限を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、数列の各要素を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

A_l + A_{l+1} + \cdots + A_r \leq K を満たす整数の組 (l, r)（1 \leq l \leq r \leq N）の個数を 1 行で出力せよ。

入力例 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

Score : 366 pts

Problem Statement

Takahashi has a sequence of N positive integers. The i-th element (1 \leq i \leq N) of this sequence is A_i.

Takahashi is interested in the sum of contiguous subarrays of this sequence. Specifically, for a pair of integers (l, r) (1 \leq l \leq r \leq N), he considers the sum of elements from the l-th to the r-th:

A_l + A_{l+1} + \cdots + A_r

Given an integer K, find the number of pairs (l, r) such that this sum is at most K.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{14}
  • 1 \leq A_i \leq 10^9
  • All inputs are integers

Input

N K
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of elements in the sequence and an integer K representing the upper bound of the sum, separated by a space.
  • The second line contains integers A_1, A_2, \ldots, A_N representing each element of the sequence, separated by spaces.

Output

Print on one line the number of pairs of integers (l, r) (1 \leq l \leq r \leq N) satisfying A_l + A_{l+1} + \cdots + A_r \leq K.

Sample Input 1

5 5
1 2 3 4 5

Sample Output 1

7

Sample Input 2

7 10
3 1 4 1 5 9 2

Sample Output 2

15

Sample Input 3

10 1000000000000
500000000 400000000 300000000 200000000 100000000 600000000 700000000 800000000 900000000 1000000000

Sample Output 3

55