Submission #6328413

---

Source Code Expand

import sys
input = sys.stdin.readline
from collections import Counter

"""
・左から見て最大値
・自分より右に、自分より以上の数がいくつあるか
・自分の下の数が何か
"""

N = int(input())
A = [int(x) for x in input().split()]

nums = sorted(set(A), reverse = True)
nums.append(0)
answer = [0] * N
counter = Counter(A)
position = dict() # その数字がある左端のインデックス
for i,a in enumerate(A):
    if not (a in position):
        position[a] = i

# 大きい数字から処理していく
for n, next_n in zip(nums[:-1], nums[1:]):
    i = position[n]
    c = counter[n]
    # 山がc個ある。i番を記録しながらnext_nに合流
    counter[n] -= c
    counter[next_n] += c
    if next_n != 0:
        position[next_n] = min(position[next_n], i)
    answer[i] += c * (n - next_n)

print('\n'.join(map(str,answer)))

Submission Info

Judge Result