D - Count Interval Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

長さ N の数列 A=(A_1,A_2,\ldots,A_N) と、整数 K が与えられます。

A の連続部分列のうち、要素の和が K になるものはいくつありますか？
すなわち、以下の条件を全て満たす整数の組 (l,r) はいくつありますか？

  • 1\leq l\leq r\leq N
  • \displaystyle\sum_{i=l}^{r}A_i = K

制約

  • 1\leq N \leq 2\times 10^5
  • |A_i| \leq 10^9
  • |K| \leq 10^{15}
  • 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

6 5
8 -3 5 7 0 -4

出力例 1

3

(l,r)=(1,2),(3,3),(2,6) の 3 組が条件を満たします。

入力例 2

2 -1000000000000000
1000000000 -1000000000

出力例 2

0

条件を満たす (l,r) の組が 1 つも存在しないこともあります。

Score : 400 points

Problem Statement

Given is a sequence of length N: A=(A_1,A_2,\ldots,A_N), and an integer K.

How many of the contiguous subsequences of A have the sum of K?
In other words, how many pairs of integers (l,r) satisfy all of the conditions below?

  • 1\leq l\leq r\leq N
  • \displaystyle\sum_{i=l}^{r}A_i = K

Constraints

  • 1\leq N \leq 2\times 10^5
  • |A_i| \leq 10^9
  • |K| \leq 10^{15}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

6 5
8 -3 5 7 0 -4

Sample Output 1

3

(l,r)=(1,2),(3,3),(2,6) are the three pairs that satisfy the conditions.

Sample Input 2

2 -1000000000000000
1000000000 -1000000000

Sample Output 2

0

There may be no pair that satisfies the conditions.