/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君は、ある商店街の N 店舗の売上データを分析しています。商店街の店舗には 1 から N までの番号が付けられており、各店舗 i の1日あたりの売上は V_i 円です。
商店街では、連続する店舗をまとめて「販売促進エリア」として指定するキャンペーンを企画しています。販売促進エリアは、整数の組 (l, r)（ 1 \leq l \leq r \leq N ）を選び、番号 l から番号 r までの連続する店舗をすべて含む形で設定します。(l, r) が異なれば、異なるエリアとして区別します。
ただし、キャンペーンの効果を十分に得るため、選んだ店舗の売上の合計が K 円以上になるエリアのみが採用されます。すなわち、V_l + V_{l+1} + \cdots + V_r \geq K を満たす必要があります。
高橋君は、採用可能な販売促進エリアが何通りあるかを知りたいと思っています。条件を満たす (l, r) の組の個数を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{14}
- 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数である
入力
N K V_1 V_2 \ldots V_N
- 1 行目には、店舗の個数を表す整数 N と、必要な売上の合計の下限を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各店舗の売上を表す整数 V_1, V_2, \ldots, V_N が、スペース区切りで与えられる。
出力
条件を満たす販売促進エリアの個数、すなわち V_l + V_{l+1} + \cdots + V_r \geq K となる組 (l, r)（ 1 \leq l \leq r \leq N ）の個数を 1 行で出力してください。なお、答えは 64 ビット整数の範囲に収まることが保証されます。
入力例 1
5 10 3 1 4 1 5
出力例 1
3
入力例 2
8 15 5 3 8 2 7 4 6 1
出力例 2
18
入力例 3
10 1000000000000 100000000 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 1000000000
出力例 3
0
Score : 366 pts
Problem Statement
Takahashi is analyzing the sales data of N stores in a shopping district. The stores in the shopping district are numbered from 1 to N, and the daily sales of each store i is V_i yen.
The shopping district is planning a campaign to designate contiguous stores as a "sales promotion area." A sales promotion area is defined by choosing a pair of integers (l, r) (1 \leq l \leq r \leq N) and including all consecutive stores from number l to number r. Different pairs (l, r) are considered distinct areas.
However, to ensure sufficient campaign effectiveness, only areas where the total sales of the selected stores is at least K yen will be adopted. That is, the condition V_l + V_{l+1} + \cdots + V_r \geq K must be satisfied.
Takahashi wants to know how many possible sales promotion areas can be adopted. Find the number of pairs (l, r) that satisfy the condition.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{14}
- 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
- All input values are integers
Input
N K V_1 V_2 \ldots V_N
- The first line contains an integer N representing the number of stores and an integer K representing the minimum required total sales, separated by a space.
- The second line contains integers V_1, V_2, \ldots, V_N representing the sales of each store, separated by spaces.
Output
Print in one line the number of sales promotion areas that satisfy the condition, that is, the number of pairs (l, r) (1 \leq l \leq r \leq N) such that V_l + V_{l+1} + \cdots + V_r \geq K. It is guaranteed that the answer fits within a 64-bit integer.
Sample Input 1
5 10 3 1 4 1 5
Sample Output 1
3
Sample Input 2
8 15 5 3 8 2 7 4 6 1
Sample Output 2
18
Sample Input 3
10 1000000000000 100000000 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 1000000000
Sample Output 3
0