/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 450 点
問題文
長さ N の数列 A=(A_1,A_2,\dots,A_N) が与えられるので、(空でない)連続部分列であって総和が L 以上 R 以下であるものの個数を答えてください。
ただし、 2 つの連続部分列が列として一致していたとしても、それらを取り出した位置が異なるのであれば、それらは区別して数えるものとします。
制約
- 入力は全て整数
- 1 \le N \le 3 \times 10^5
- -10^{18} \le L \le R \le 10^{18}
- -10^{12} \le A_i \le 10^{12}
入力
入力は以下の形式で標準入力から与えられる。
N L R A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
5 -2 3 3 -1 -4 -1 5
出力例 1
8
この入力では、 l 項目から r 項目までからなる連続部分列が条件を満たすような (l,r) の組は以下の 8 個です。
- (1,1),(1,2),(1,3),(1,5),(2,2),(2,5),(3,5),(4,4)
入力例 2
6 0 0 0 0 0 0 0 0
出力例 2
21
L=R である場合もあります。
入力例 3
10 -126566 92319 11087 76694 -94782 -28589 -77903 -75549 31253 60353 -69062 -49587
出力例 3
34
Score : 450 points
Problem Statement
You are given a sequence A=(A_1,A_2,\dots,A_N) of length N. Find the number of (non-empty) contiguous subsequences whose sum is between L and R, inclusive.
Here, even if two contiguous subsequences are equal as sequences, they are counted separately if they are taken from different positions.
Constraints
- All input values are integers.
- 1 \le N \le 3 \times 10^5
- -10^{18} \le L \le R \le 10^{18}
- -10^{12} \le A_i \le 10^{12}
Input
The input is given from Standard Input in the following format:
N L R A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
5 -2 3 3 -1 -4 -1 5
Sample Output 1
8
For this input, there are 8 pairs (l,r) such that the contiguous subsequence from the l-th through r-th elements satisfies the condition:
- (1,1),(1,2),(1,3),(1,5),(2,2),(2,5),(3,5),(4,4)
Sample Input 2
6 0 0 0 0 0 0 0 0
Sample Output 2
21
It is possible that L=R.
Sample Input 3
10 -126566 92319 11087 76694 -94782 -28589 -77903 -75549 31253 60353 -69062 -49587
Sample Output 3
34