/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
長さ N の非負整数列 A = (A_1, \dots, A_N) が与えられます。
k = 1, \dots, N について、次の問題を解いてください。
- A の連続部分列のうち長さが k のものは N-k+1 個ある。それぞれの連続部分列について最大値を求めたとき、それらの合計を求めよ。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 10^7 (1 \leq i \leq N)
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
N 行出力せよ。i 行目 (1 \leq i \leq N) には、k = i に対する答えを出力せよ。
入力例 1
4 5 3 4 2
出力例 1
14 13 9 5
k = 1 の場合、長さ k=1 の連続部分列は 4 個あり、それぞれについて
- (5) の最大値は 5
- (3) の最大値は 3
- (4) の最大値は 4
- (2) の最大値は 2
となり、これらの合計は 5+3+4+2 = 14 です。
k = 2 の場合、長さ k=2 の連続部分列は 3 個あります。それぞれについて
- (5,3) の最大値は 5
- (3,4) の最大値は 4
- (4,2) の最大値は 4
となり、これらの合計は 5+4+4 = 13 です。
k = 3 の場合、長さ k=3 の連続部分列は 2 個あります。それぞれについて
- (5,3,4) の最大値は 5
- (3,4,2) の最大値は 4
となり、これらの合計は 5+4 = 9 です。
k = 4 の場合、長さ k=4 の連続部分列は 1 個あります。それぞれについて
- (5,3,4,2) の最大値は 5
となり、これらの合計は 5 です。
入力例 2
8 2 0 2 5 0 5 2 4
出力例 2
20 28 27 25 20 15 10 5
入力例 3
11 9203973 9141294 9444773 9292472 5507634 9599162 497764 430010 4152216 3574307 430010
出力例 3
61273615 68960818 69588453 65590626 61592799 57594972 47995810 38396648 28797486 19198324 9599162
Score : 550 points
Problem Statement
You are given a sequence of non-negative integers A = (A_1,\dots,A_N) of length N.
For each k = 1,\dots,N, solve the following problem:
- A has N-k+1 (contiguous) subarrays of length k. Take the maximum of each of them, and output the sum of these maxima.
Constraints
- 1 \le N \le 2 \times 10^{5}
- 0 \le A_i \le 10^{7} (1 \le i \le N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Output N lines. The i-th line (1 \le i \le N) should contain the answer for k = i.
Sample Input 1
4 5 3 4 2
Sample Output 1
14 13 9 5
For k = 1, there are four subarrays of length k=1:
- (5), whose maximum is 5;
- (3), whose maximum is 3;
- (4), whose maximum is 4;
- (2), whose maximum is 2.
The sum is 5 + 3 + 4 + 2 = 14.
For k = 2, there are three subarrays of length k=2:
- (5,3), whose maximum is 5;
- (3,4), whose maximum is 4;
- (4,2), whose maximum is 4.
The sum is 5 + 4 + 4 = 13.
For k = 3, there are two subarrays of length k=3:
- (5,3,4), whose maximum is 5;
- (3,4,2), whose maximum is 4.
The sum is 5 + 4 = 9.
For k = 4, there is one subarray of length k=4:
- (5,3,4,2), whose maximum is 5.
The sum is 5.
Sample Input 2
8 2 0 2 5 0 5 2 4
Sample Output 2
20 28 27 25 20 15 10 5
Sample Input 3
11 9203973 9141294 9444773 9292472 5507634 9599162 497764 430010 4152216 3574307 430010
Sample Output 3
61273615 68960818 69588453 65590626 61592799 57594972 47995810 38396648 28797486 19198324 9599162