/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
正整数 S が与えられます． 正整数列 x に対し，f(x) を以下のように定めます．
- x をいくつかの連続部分列に分解することを考える． このとき，どの連続部分列についても要素の総和が S 以下でなくてはならない． このような分解における連続部分列の個数の最小値を f(x) の値とする．
なお，この問題の制約下では f の値が必ず定義できることが証明できます．
正整数列 A=(A_1,A_2,\cdots,A_N) が与えられます． \sum_{1 \leq l \leq r \leq N} f((A_l,A_{l+1},\cdots,A_r)) の値を求めてください．
制約
- 1 \leq N \leq 250000
- 1 \leq S \leq 10^{15}
- 1 \leq A_i \leq \min(S,10^9)
- 入力される値はすべて整数．
入力
入力は以下の形式で標準入力から与えられる．
N S A_1 A_2 \cdots A_N
出力
答えを出力せよ．
入力例 1
3 3 1 2 3
出力例 1
8
例えば x=(1,2,3) を考えると，(1,2),(3) という分解が条件を満たし， かつ 2 個未満の連続部分列に分解した場合は条件を満たさないため，f((1,2,3))=2 です．
ありうる l,r とそれに対応する f の値は以下の通りです．
- (l,r)=(1,1): f((1))=1
- (l,r)=(1,2): f((1,2))=1
- (l,r)=(1,3): f((1,2,3))=2
- (l,r)=(2,2): f((2))=1
- (l,r)=(2,3): f((2,3))=2
- (l,r)=(3,3): f((3))=1
よって答えは 1+1+2+1+2+1=8 になります．
入力例 2
5 1 1 1 1 1 1
出力例 2
35
入力例 3
5 15 5 4 3 2 1
出力例 3
15
入力例 4
20 1625597454 786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130
出力例 4
588
Score : 500 points
Problem Statement
You are given a positive integer S. For a sequence of positive integers x, we define f(x) as follows:
- Consider decomposing x into several contiguous subsequences. For each contiguous subsequence, the sum of its elements must be at most S. The minimum number of contiguous subsequences in such a decomposition is the value of f(x).
It can be proved that the value of f is always definable under the constraints of this problem.
You are given a sequence of positive integers A=(A_1,A_2,\cdots,A_N). Find the value of \sum_{1 \leq l \leq r \leq N} f((A_l,A_{l+1},\cdots,A_r)).
Constraints
- 1 \leq N \leq 250000
- 1 \leq S \leq 10^{15}
- 1 \leq A_i \leq \min(S,10^9)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N S A_1 A_2 \cdots A_N
Output
Print the answer.
Sample Input 1
3 3 1 2 3
Sample Output 1
8
For example, consider x=(1,2,3). The decomposition (1,2),(3) satisfies the condition, and no decomposition into fewer than two contiguous subsequences satisfies the condition, so f((1,2,3))=2.
Shown below are the possible l,r and the corresponding values of f:
- (l,r)=(1,1): f((1))=1
- (l,r)=(1,2): f((1,2))=1
- (l,r)=(1,3): f((1,2,3))=2
- (l,r)=(2,2): f((2))=1
- (l,r)=(2,3): f((2,3))=2
- (l,r)=(3,3): f((3))=1
Thus, the answer is 1+1+2+1+2+1=8.
Sample Input 2
5 1 1 1 1 1 1
Sample Output 2
35
Sample Input 3
5 15 5 4 3 2 1
Sample Output 3
15
Sample Input 4
20 1625597454 786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130
Sample Output 4
588