/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 433 点
問題文
高橋君は、N 個の整数からなる数列 A_1, A_2, \ldots, A_N を持っています。
高橋君は、この数列から連続する区間を 1 つ選びたいと考えています。具体的には、整数の組 (l, r)（1 \leq l \leq r \leq N）を 1 つ選び、l 番目から r 番目までの要素を取り出します。
このとき、選んだ区間のスコアを次のように定義します。
f(l, r) = \sum_{i=l}^{r} A_i + (r - l + 1) \times M
すなわち、区間に含まれる要素の合計に、区間の長さ (r - l + 1) と正の整数 M の積を加えた値です。
スコアが K 以下となるような整数の組 (l, r)（1 \leq l \leq r \leq N）の個数を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 10^9
- 1 \leq K \leq 10^{18}
- -10^9 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数
入力
N M K A_1 A_2 \cdots A_N
- 1 行目には、数列の長さ N、スコアの係数 M、スコアの上限 K が、スペース区切りで与えられる。
- 2 行目には、数列の各要素 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
スコアが K 以下となる整数の組 (l, r)（1 \leq l \leq r \leq N）の個数を 1 行で出力してください。
入力例 1
5 2 10 1 3 2 4 1
出力例 1
9
入力例 2
7 3 20 -2 5 -1 4 3 -3 2
出力例 2
22
入力例 3
10 1000000000 5000000000 100 -500 300 200 -100 400 -200 150 250 -50
出力例 3
35
Score : 433 pts
Problem Statement
Takahashi has a sequence of N integers A_1, A_2, \ldots, A_N.
Takahashi wants to select one contiguous interval from this sequence. Specifically, he chooses a pair of integers (l, r) (1 \leq l \leq r \leq N) and extracts the elements from the l-th to the r-th.
The score of the chosen interval is defined as follows:
f(l, r) = \sum_{i=l}^{r} A_i + (r - l + 1) \times M
That is, the score is the sum of the elements in the interval plus the product of the interval length (r - l + 1) and a positive integer M.
Find the number of integer pairs (l, r) (1 \leq l \leq r \leq N) such that the score is at most K.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 10^9
- 1 \leq K \leq 10^{18}
- -10^9 \leq A_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers.
Input
N M K A_1 A_2 \cdots A_N
- The first line contains the length of the sequence N, the score coefficient M, and the score upper bound K, separated by spaces.
- The second line contains the elements of the sequence A_1, A_2, \ldots, A_N, separated by spaces.
Output
Print in one line the number of integer pairs (l, r) (1 \leq l \leq r \leq N) such that the score is at most K.
Sample Input 1
5 2 10 1 3 2 4 1
Sample Output 1
9
Sample Input 2
7 3 20 -2 5 -1 4 3 -3 2
Sample Output 2
22
Sample Input 3
10 1000000000 5000000000 100 -500 300 200 -100 400 -200 150 250 -50
Sample Output 3
35