/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 433 点
問題文
高橋君は N 個の整数からなる数列 A = (A_1, A_2, \ldots, A_N) を持っています。各要素 A_i は負の値をとることもあります。
高橋君はこの数列から連続する区間を選び、その要素の総和がちょうど整数 K に等しくなるようにしたいと考えています。ここで K は目標とする総和の値です。そのような区間の選び方が何通りあるかを求めてください。
より正確には、1 \leq l \leq r \leq N を満たす整数の組 (l, r) であって、
$$A_l + A_{l+1} + \cdots + A_r = K$$
を満たすものの個数を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq K \leq 10^9
- -10^9 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N K A_1 A_2 \cdots A_N
- 1 行目には、数列の要素数を表す整数 N と、目標とする総和の値を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、数列の各要素を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
条件を満たす整数の組 (l, r) の個数を 1 行で出力せよ。
入力例 1
5 5 1 2 3 4 5
出力例 1
2
入力例 2
6 3 1 -1 2 3 -2 4
出力例 2
3
入力例 3
10 0 1 -1 0 0 2 -2 0 3 -3 0
出力例 3
28
Score : 433 pts
Problem Statement
Takahashi has a sequence of N integers A = (A_1, A_2, \ldots, A_N). Each element A_i may take a negative value.
Takahashi wants to select a contiguous subarray from this sequence such that the sum of its elements is exactly equal to the integer K, where K is the target sum value. Find the number of ways to choose such a subarray.
More precisely, find the number of pairs of integers (l, r) satisfying 1 \leq l \leq r \leq N such that
$$A_l + A_{l+1} + \cdots + A_r = K$$
Constraints
- 1 \leq N \leq 2 \times 10^5
- -10^9 \leq K \leq 10^9
- -10^9 \leq A_i \leq 10^9
- All inputs are integers
Input
N K A_1 A_2 \cdots A_N
- The first line contains the integer N representing the number of elements in the sequence and the integer K representing the target sum value, separated by a space.
- The second line contains the integers A_1, A_2, \ldots, A_N representing each element of the sequence, separated by spaces.
Output
Print the number of pairs of integers (l, r) that satisfy the condition, on a single line.
Sample Input 1
5 5 1 2 3 4 5
Sample Output 1
2
Sample Input 2
6 3 1 -1 2 3 -2 4
Sample Output 2
3
Sample Input 3
10 0 1 -1 0 0 2 -2 0 3 -3 0
Sample Output 3
28