Problem:


Score : 700 points

Problem Statement

Snuke loves constructing integer sequences.

There are N piles of stones, numbered 1 through N.
The pile numbered i consists of a_i stones.

Snuke will construct an integer sequence s of length Σa_i, as follows:

Among the piles with the largest number of stones remaining, let x be the index of the pile with the smallest index. Append x to the end of s.

Select a pile with one or more stones remaining, and remove a stone from that pile.

If there is a pile with one or more stones remaining, go back to step 1. Otherwise, terminate the process.

We are interested in the lexicographically smallest sequence that can be constructed. For each of the integers 1,2,3,...,N, how many times does it occur in the lexicographically smallest sequence?

Constraints

1 ≤ N ≤ 10^{5}

1 ≤ a_i ≤ 10^{9}

Input

The input is given from Standard Input in the following format:

N
a_1 a_2 ... a_{N}

Output

Print N lines. The i-th line should contain the number of the occurrences of the integer i in the lexicographically smallest sequence that can be constructed.

Sample Input 1

2
1 2

Sample Output 1

2
1

The lexicographically smallest sequence is constructed as follows:

Since the pile with the largest number of stones remaining is pile 2, append 2 to the end of s. Then, remove a stone from pile 2.

Since the piles with the largest number of stones remaining are pile 1 and 2, append 1 to the end of s (we take the smallest index). Then, remove a stone from pile 2.

Since the pile with the largest number of stones remaining is pile 1, append 1 to the end of s. Then, remove a stone from pile 1.

The resulting sequence is (2,1,1). In this sequence, 1 occurs twice, and 2 occurs once.

Sample Input 2

10
1 2 1 3 2 4 2 5 8 1

Sample Output 2

10
7
0
4
0
3
0
2
3
0



Sample input:
2
1 2


Sample output:
2
1

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input().rstrip("\n"))
piles = map(int, raw_input().rstrip("\n").split(" "))

limits = [(0, piles[0])]
from collections import defaultdict
counter = defaultdict(int)
for i , pile in enumerate(piles):
  count = pile
  for pile_index, limit in limits:
    if count <= limit:
      counter[pile_index] += count
      count = 0
    else:
      counter[pile_index] += limit
      count -= limit
    if count == 0:
      break
  if count > 0:
    limits.append((i, count))
    counter[i] += count

for i in xrange(n):
  print counter[i]

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = [0 for i in range(n)]

max_a = max(a)
i = a.index(max_a)

while i != 0:
    max_left = max(a[0:i])
    i_left = a[0:i].index(max_left)

    tmp = 0
    for j in range(i, n):
        # print(j, a[j], max_left)
        if a[j] > max_left:
            tmp += a[j] - max_left
            a[j] = max_left
    ans[i] += tmp

    i = i_left

for j in range(n):
    tmp = 0
    if a[j] > 0:
        tmp += a[j]
        a[j] = 0
    ans[0] += tmp

for j in range(n):
    print(ans[j])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
ans = [0 for i in range(n)]

max_a = max(a)
i = a.index(max_a)

while i != 0:
    max_left = max(a[0:i])
    i_left = a[0:i].index(max_left)

    tmp = 0
    for j in range(i, n):
        # print(j, a[j], max_left)
        if a[j] > max_left:
            tmp += a[j] - max_left
            a[j] = max_left
    ans[i] += tmp

    i = i_left

for j in range(n):
    tmp = 0
    if a[j] > 0:
        tmp += a[j]
        a[j] = 0
    ans[0] += tmp

for i in range(n):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
a = map(int, raw_input().split())

for i in range(n):
    ans = 0
    for j in reversed(range(n)):
        if a[j] < a[i]:
            ans += a[j]
            a[j] = 0
        else:
            ans += a[i]
            a[j] -= a[i]
    print ans

Submission status: Time Limit Exceeded

Solution code:
n = int(input().strip())
data = list(map(int, input().split()))
res = [0] * n
cur = 0 
ind = []
cut = [0]
for (i, v) in enumerate(data):
  if v > cur:
    cur = v
    cut.append(v)
    ind.append(i)

for v in data:
  for i, x, y in zip(ind, cut, cut[1:]):
    if x > v: break
    res[i] += max(0, min(v, y) - x)
    
for v in res:
  print(v)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
a = [int(x) for x in input().split()]
a = np.array(a)

def find_next(k, a, rest, a_k):
  k_next = np.argmax(a[:k])
  a_k_next = a[k_next]
  a_back = a[k:]
  a_back_filtered = a_back[a_back >= a_k_next]
  num_k = np.sum(a_back_filtered - a_k_next) + rest * (a_k - a_k_next)
  a_back2 = a[k_next:]
  rest_next = rest + len(a_back2[a_back2 >= a_k_next])
  a_next = np.concatenate([a[:k_next], a_back2[a_back2 < a_k_next]])
  return k_next, a_k_next, num_k, rest_next, a_next

def solve(n, a):
  k = n
  rest = 0
  a_k = 0
  d = [0] * n
  while k > 0:
    k_m, a_k, num_k, rest, a = find_next(k, a, rest, a_k)
    if k != n:
      d[k] = num_k
    k = k_m
  d[0] = np.sum(a) + rest * a_k

  return d

result = solve(n, a)
for x in result:
  print(x)

Submission status: Time Limit Exceeded

Solution code:
n = int(input().strip())
data = list(map(int, input().split()))
res = [0] * n
old_m = None
while n >= 0:
  if n > 0:
    m = max(data[:n])
    nn = data.index(m)
  else:
    m = 0
    nn = -1
  if old_m:
    res[n] = sum([max(0, min(v, old_m) - m) for v in data])
  old_m = m
  n = nn  
for v in res:
  print(v)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import collections

input()
a = [int(x) for x in input().split()]
c = collections.Counter()
ranking = sorted(range(len(a)), key=lambda i: -a[i])

for _ in range(sum(a)):
    mi, _ = max(enumerate(a), key=lambda x: x[1])
    c[mi] += 1

    # print('gen', ranking)
    # ra = sorted(range(len(a)), key=lambda i: -a[i])
    # wrong = any(x != y for x, y in zip(ranking, ra))
    # print('tru', ra if wrong else '')
    # print('a  ', a)
    # print()

    i = 0
    while i < len(a) - 1 and ranking[i] <= ranking[i + 1]:
        i += 1

    a[ranking[i]] -= 1
    if i < len(a) - 1 and a[ranking[i]] <= a[ranking[i + 1]]:
        ranking = sorted(range(len(a)), key=lambda i: -a[i])
        # t = ranking[i]
        # ranking[i] = ranking[i + 1]
        # ranking[i + 1] = t

print(*[c[i] for i in range(len(a))], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import collections

input()
a = [int(x) for x in input().split()]
c = collections.Counter()

for _ in range(sum(a)):
    mi, _ = max(enumerate(a), key=lambda x: x[1])
    c[mi] += 1

    ranking = sorted(range(len(a)), key=lambda i: -a[i])
    while len(ranking) > 1 and not ranking[0] > ranking[1]:
        ranking = ranking[1:]
    a[ranking[0]] -= 1

print(*[c[i] for i in range(len(a))], sep='\n')

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))

ans = [0] * (n+1)
d = dict()
for i,ai in enumerate(a,1):
    if(ai in d):
        d[ai][1] += 1
    else:
        d[ai] = [i,1]
d[0] = [0,0]

a_unique = list(set(a))
a_unique.sort(reverse=True)
a_unique.append(0)

for i in range(len(a_unique)-1):
    num = a_unique[i]
    next = a_unique[i+1]
    head = d[num][0]
    ans[head] += (num-next) * d[num][1]

    d[next][0] = min(d[next][0],d[num][0])
    d[next][1] += d[num][1]

print('\n'.join(map(str,ans[1:])))

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

b = sorted([(i+1, a[i]) for i in range(n)], key=lambda x: -x[1])
ans = [0]*(n+1)
m = float('inf')
for i in range(n-1):
    m = min(m, b[i][0])
    if b[i][1] == b[i+1][1]:
        continue
    ans[m] += (i+1)*(b[i][1]-b[i+1][1])
ans[1] += sum(a) - sum(ans)
for i in range(1, n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))

L = list(range(1, N+1))

ZIP = zip(A, L)

ZIP = sorted(ZIP, reverse = True)

A, L = zip(*ZIP)

ans = [0] * (N + 1)

MIN = float('INF')

for i in range(N-1):
    MIN = min(MIN, L[i])
    if A[i] - A[i+1] == 0:
        continue
    ans[MIN] += (A[i] - A[i+1]) * (i + 1)
ans[1] += sum(A) - sum(ans)

for i in range(1, N+1):
    print(ans[i])

Submission status: Accepted

Solution code:
from sys import exit
from collections import Counter
n = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)
ans = [0 for _ in range(n)]
D = dict()
S = set(A)
if len(S) == 1:
    print(sum(A))
    for _ in range(n - 1):
        print(0)
    exit()
X = sorted(S, reverse=True)
for i, x in enumerate(X):
    D[x] = i

index = [n + 1 for _ in range(len(S))]
for i, a in enumerate(A):
    index[D[a]] = min(index[D[a]], i)

cnt = 0
x = n + 1

for i in range(1, len(S)):
    tmp = X[i - 1]
    nxt = X[i]
    cnt += C[tmp]
    x = min(x, index[D[tmp]])
    ans[x] += (tmp - nxt) * cnt

for i, a in enumerate(A):
    if a != 0:
        cnt += C[nxt]
        ans[i] += nxt * cnt
        break

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
b = [(a[i],i) for i in range(n)]
b.sort(reverse=True)
b.append((0,0))
ans = [0]*n
v = b[0][1]
for i in range(n):
    ans[v] += (i+1)*(b[i][0]-b[i+1][0])
    v = min(v,b[i+1][1])
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(enumerate(map(int, input().split())))

    a.sort(key=lambda x: x[1], reverse=True)
    a.append((-1, 0))

    # min_ind = min(a[:i+1])[0]
    min_ind = n
    ans = [0] * n
    for i in range(n):
        ind, value = a[i]
        if ind < min_ind:
            min_ind = ind

        ans[min_ind] += (value - a[i+1][1]) * (i+1)

    for i in ans:
        print(i)

main()

Submission status: Accepted

Solution code:
def main(n,a):
  ret=[0]*n
  d={}
  for i,x in enumerate(a):
    if x in d:
      d[x].append(i)
    else:
      d[x]=[i]
  v=sorted(list(d.keys()),reverse=True)
  cnt_idx=0
  min_idx=n+1
  for i,x in enumerate(v):
    cnt_idx+=len(d[x])
    min_idx=min(min_idx,d[x][0])
    nx=0
    if i<len(v)-1:nx=v[i+1]
    ret[min_idx]+=cnt_idx*(x-nx)
  return ret

n=int(input())
a=list(map(int,input().split()))
print(*main(n,a),sep='\n')

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n = int(ipt())
    ans = [0]*n
    a = [int(i) for i in ipt().split()]
    cts = [(a[0],0)]
    d = defaultdict(int)
    d[a[0]] = 1
    tot = a[0]
    for i,ai in enumerate(a[1::]):
        tot += ai
        d[ai] += 1
        if cts[-1][0] < ai:
            cts.append((ai,i+1))

#    print(d,cts)
    nms = sorted(d.keys(),reverse=True)
    lc = len(cts)-1
    na = cts[lc][0]
    ps = cts[lc][1]
    sm = 0
    for i in nms:
        sm += d[i]
        if i == na:
            lc -= 1
            na = cts[lc][0]
            ans[ps] += sm*(i-na)
            pps = ps
            ps = cts[lc][1]
        else:
            ans[pps] += d[i]*(i-na)
#        print(ans)

    ans[0] = tot-sum(ans[1::])

    for i in ans:
        print(i)



    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))

sorted_iAs = sorted(map(tuple, enumerate(As)), key = lambda t: (t[1], t[0]), reverse = True)

#if As = 1 2 1 3 2 4 2 5 8 1
#then sorted_iAs is:
#   i | 8 7 5 3 6 4 1 9 2 0
#   A | 8 5 4 3 2 2 2 1 1 1
#I'll look at:
#       x x x x     x     x
#where the next A decreases (or doesn't exist).

ans = [0] * N
youngest_index = 10 ** 9
for index, (original_index, A) in enumerate(sorted_iAs):
    youngest_index = min(original_index, youngest_index)
    if index == N - 1:
        ans[youngest_index] += A * (index + 1)
    elif sorted_iAs[index + 1][1] < A:
        next_A = sorted_iAs[index + 1][1]
        ans[youngest_index] += (A - next_A) * (index + 1)

print(*ans, sep = '\n')

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=sorted([(i,a) for i,a in enumerate(A)],key=lambda x:x[1])[::-1]+[(N,0)]
d=[0]*N
m=N
for i in range(N):
    m=min(m,B[i][0])
    d[m]+=(i+1)*(B[i][1]-B[i+1][1])
print(*d,sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from itertools import accumulate
N = int(input())
A = list(map(int,input().split()))

inf = 10**10

S = [0] + sorted(list(set(A)))
dic = {s:inf for s in S}
cnt = {s:0 for s in S}
sm = {s:0 for s in S}
ml = [0]
for i, a in enumerate(A):
    if ml[-1] < a:
        ml.append(a)
    dic[a] = min(i,dic[a])
    cnt[a] += 1
    sm[a] += a

for ps, s in zip(S[:-1][::-1],S[::-1]):
    cnt[ps] += cnt[s]
    sm[ps] += sm[s]

ans = [0]*N
temp = {s:sm[s] - s*cnt[s] for s in S}

for ps, s in zip(ml[:-1][::-1],ml[::-1]):
    ans[dic[s]] = temp[ps] - temp[s]

[print(a) for a in ans]

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,*a = map(int,read().split())

res = [(0,-1)]+[(a[i],i) for i in range(n)]
res.sort()

ans = [0]*n
num = 0
cnt = 0
midx = idx = n-1
v = res[-1][0]

#print(res)
while res:
    #print(num,cnt,idx)
    ans[midx] += (v-res[-1][0])*cnt
    v = res[-1][0]

    while res and res[-1][0]==v:
        ai,idx = res.pop()        
        cnt += 1
    midx = min(midx,idx)

print(*ans,sep="\n")

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
*a, = map(int, input().split())

cnt = defaultdict(int)
pos = defaultdict(lambda :10**12)
ans = defaultdict(int)

for i, j in enumerate(a, start=1):
    pos[j] = min(pos[j], i)
    cnt[j] += 1

target = [list(i) for i in sorted(pos.items())][::-1]
size = len(target)

for i in range(len(target)-1):
    a, b = target[i]
    c, d = target[i+1]
    ans[b] += cnt[a]*(a-c)
    cnt[c] += cnt[a]
    cnt[a] = 0
    target[i+1][1] = min(target[i+1][1], b)

a = target[-1][0]
ans[1] += cnt[a]*a
for i in range(1, N+1):
    print(ans[i])

Submission status: Accepted

Solution code:
# frequency
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
seq = []
freq = [0 for i in range(N+1)]
D = defaultdict(list)
minD = defaultdict(int)
for i, v in enumerate(A):
    D[v].append(i+1)
for key in D.keys():
    minD[key] = min(D[key])
for cnt in D.keys():
    seq.append((cnt, len(D[cnt]), minD[cnt]))
seq.append((0, 0, 0))
seq.sort(key=lambda x: -x[0])
now_height, now_size, now_min = seq[0]
# howmany,group_size,minimum
for i in range(1, len(seq)):
    freq[now_min] += (now_height-seq[i][0]) * now_size
    now_min = min(now_min, seq[i][2])
    now_size += seq[i][1]
    now_height = seq[i][0]
for i in range(1, N+1):
    print(freq[i])

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from bisect import bisect_left, bisect_right, insort

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

""" 
石数最大の中で右の山から取り除く
次の数までまとめて石を取り除く
"""
N = ir()
A = lr()
A = [(x, i+1) for i, x in enumerate(A)] + [(0, 0)]
A.sort(reverse=True)
answer = [0] * (N+1)  # 1-indexed
mi = 10 ** 10
mi_index = 10 ** 10
for i, (x, pre_index) in enumerate(A[:-1]):
    diff = A[i][0] - A[i+1][0]
    if pre_index < mi_index:
        mi_index = pre_index
    answer[mi_index] += diff * (i+1)

print('\n'.join(map(str, answer[1:])))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from bisect import bisect_left, bisect_right, insort

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

""" 
左側で自分より小さい数字との差
右側で自分より大きい数字の数
石数最大の山で右の物から取り除く
"""
N = ir()
A = lr()
A = [(x, i+1) for i, x in enumerate(A)] + [(0, 0)]
A.sort(reverse=True)
answer = [0] * (N+1)  # 1-indexed
mi = 10 ** 10
mi_index = 10 ** 10
for i, (x, j) in enumerate(A[:-1]):
    diff = A[i][0] - A[i+1][0]
    index = A[i][1]
    if index < mi_index:
        mi_index = index
    answer[mi_index] += diff * (i+1)

print('\n'.join(map(str, answer[1:])))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
a = [(-num, i) for i,num in enumerate(a)]
a.append((0, -1))
import heapq
heapq.heapify(a)
ans = [0]*n

pnum, pi = heapq.heappop(a)
pnum *= -1
count = 1
v = pnum
while a:
    num, i = heapq.heappop(a)
    num *= -1
    if i<pi:
        ans[pi] = v - num*count
        v = num*(count+1)
        count += 1
        pi = i
    else:
        count += 1
        v += num
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read

n, *A = map(int, read().split())
S = sorted([(a, i) for i, a in enumerate(A)], reverse=True)
X, Y = zip(*S)
m = 10**9
L = [0]*n
for i, y in enumerate(Y):
  m = min(m, y)
  if i == n-1:
    L[m] += (i+1) * X[i]
  else:
    L[m] += (i+1) * (X[i] - X[i+1])
print(*L, sep="\n")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = [[a[i], i] for i in range(n)]
b.sort(reverse = True)
d = {}
dcnt = {}
for i in range(n):
    if not a[i] in d:
        d[a[i]] = i
        dcnt[a[i]] = 1
    else:
        dcnt[a[i]] = dcnt[a[i]] + 1
b = [[0, 0] for _ in range(len(d) + 1)]
k = 0
for i, j in d.items():
    b[k][0], b[k][1] = i, j
    k += 1
b.sort(reverse = True)
ans = [0] * n
j = b[0][1]
cnt = 0
for i in range(len(d)):
    cnt += dcnt[b[i][0]]
    j = min(j, b[i][1])
    ans[j] += (b[i][0] - b[i + 1][0]) * cnt
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
import heapq
import sys
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 10 ** 9 + 7
def mint(lis):
    return list(map(int, lis))

def bifind(arr_sorted, x):
    idx = bisect_left(arr_sorted, x)
    if idx == len(arr_sorted):
        return False
    if arr_sorted[idx] == x:
        return True
    else:
        return False
def getyaku(n):
    ret = []
    for i in range(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            ret.append(i)
            ret.append(n // i)

    return ret

def find(x, a):
    idx = bisect_left(a, x)
    if idx == len(a):
        return False
    if a[idx] == x:
        return True
    else:
        return False

def main():
    n = getN()
    nums = getList()
    nums = [(x, i+1) for i, x in enumerate(nums)]
    nums.append((0, INF))
    nums.sort(key=lambda x: -x[0] * INF + x[1])
    # print(nums)
    mx = INF
    ans = [0 for i in range(n+1)]
    tmp_tgt = INF
    through = 0
    for a,b in nums:
        if a != mx:
            diff = mx - a



            if mx != INF:
                ans[tmp_tgt] += through * diff
            mx = a
            if b < tmp_tgt:
                tmp_tgt = b
        through += 1
    for an in ans[1:]:
        print(an)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
d = dd(int)
l = dd(lambda: N + 1)
for i in range(N):
  d[a[i]] += 1
  l[a[i]] = min(l[a[i]], i + 1)

#print(d, l)
ks = sorted(d.keys(), reverse = True)
res = [0] * (N + 1)
for i in range(len(ks) - 1):
  t = ks[i] - ks[i + 1]
  k = ks[i]
  res[l[k]] += d[k] * t
  d[ks[i + 1]] += d[k]
  l[ks[i + 1]] = min(l[ks[i + 1]], l[k])
res[1] += d[ks[-1]] * ks[-1]
for r in res[1: ]: print(r)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]

ans = [0]*N
num = 0
B = sorted(A)
j = 0
for i in range(N):
    cnt = 0
    while j < N and B[j] <= A[i]:
        cnt += max(0, B[j]-num)
        j += 1
    ans[i] = cnt + max(0, (N-j)*(A[i]-num))
    num = max(num, A[i])

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from bisect import bisect_right

n = int(input())
a = list(map(int, input().split()))

li = [[0, -1]]
for i, e in enumerate(a):
    if e > li[-1][0]:
        li.append([e, i])

li = li[::-1]

a.sort()
acc = [0] * (n + 1)
for i in range(n - 1, -1, -1):
    acc[i] = acc[i+1] + a[i]

ans = [0] * n
sub = 0
ans_prev = 0
for (ep, ip), (e, i) in zip(li, li[1:]):
    j = bisect_right(a, e)
    ans[ip] = acc[j] - e * (n - j)

i_prev = 0
for i in range(1, n):
    if ans[i]:
        ans[i_prev] -= ans[i]
        i_prev = i

print(*ans, sep="\n")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

tmp = [[e, n - i] for i, e in enumerate(a)]
tmp.sort(reverse=True)

aa = [[e, n - i] for e, i in tmp] + [[0, -1]]

v_prev, i_prev = aa[0]
i = 0
ans = [0] * n
sm = 0
while i < n:
    while aa[i][1] >= i_prev:
        sm += aa[i][0]
        i += 1

    ans[i_prev] += sm - aa[i][0] * i
    sm = aa[i][0] * i
    v_prev, i_prev = aa[i]

print(*ans, sep="\n")

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
N = int(input())
A = [0] + list(map(int, input().split()))
C = Counter(A)

value = sorted(set(A), reverse=True)
a_to_i = defaultdict(int)

for i, a in enumerate(A):
    if not a_to_i[a]:
        a_to_i[a] = i

ans = [0] * (N + 1)
cnt = 0
i = N
for x, y in zip(value[:-1], value[1:]):
    i = min(i, a_to_i[x])
    cnt += C[x]
    ans[i] += (x - y) * cnt

print(*ans[1:], sep="\n")

Submission status: Accepted

Solution code:
from collections import defaultdict
def solve():
    N = int(input())
    A = list(map(int, input().split()))
    ans = [0]*N
    min_inds = defaultdict(lambda: 10**5)
    nums = defaultdict(lambda: 0)
    for ind,a in enumerate(A):
        min_inds[a] = min(min_inds[a],ind)
        nums[a] += 1
    min_inds = sorted(list(map(list,min_inds.items())), key=lambda x:x[0])
    min_inds.append([10**9+1,10**5])
    nums = sorted(list(map(list,nums.items())), key=lambda x:x[0])
    nums.append([0,0])
    for i in range(len(min_inds)-2,-1,-1):
        min_inds[i][1] = min(min_inds[i][1],min_inds[i+1][1])
        nums[i][1] += nums[i+1][1]
        ans[min_inds[i][1]] += nums[i][1]*(nums[i][0]-nums[i-1][0])
    return ans
print(*solve(),sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
aa = list(set(a))
aa.sort()
compress = {aa[i]: i for i in range(len(aa))}
cnt = [0] * len(aa)
idx = [-1] * len(aa)
for i in range(N)[::-1]:
    n = compress[a[i]]
    cnt[n] += 1
    idx[n] = i
ans = [0] * N
for n in range(1, len(aa))[::-1]:
    i = idx[n]
    ans[i] += cnt[n] * (aa[n] - aa[n-1])
    cnt[n-1] += cnt[n]
    idx[n-1] = min(idx[n-1], i)
ans[0] += N * aa[0]
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import bisect

N=int(input())
A=list(map(int,input().split()))

inc=[[A[0],0]]
for i in range(1,N):
    if A[i]>inc[-1][0]:
        inc.append([A[i],i])

n=len(inc)
test=inc[:n-1]
query=[[] for i in range(n)]
for i in range(0,N):
    r=bisect.bisect_left(test,[A[i],i])
    query[r].append(A[i])

ans=[0 for i in range(N)]
count=0
for i in range(n-1,0,-1):
    fr=inc[i][0]
    to=inc[i-1][0]
    val=count*(fr-to)+sum(query[i])-to*len(query[i])
    ans[inc[i][1]]=val
    count+=len(query[i])

fr=inc[0][0]
to=0
val=count*(fr-to)+sum(query[0])-to*len(query[0])
ans[0]=val

for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
N = int(input())
A = [0] + list(map(int, input().split()))

# 実体Bと大きい順にループを回してindexを取得するためだけのC
B = [[a, i, 1] for i, a in enumerate(A)]
C = sorted(B, reverse=True)

# 自分より左側で最大となる値と位置
# 最大となる値が複数ある場合は最も左のものを採用
a_max, idx = 0, 0 # [value, idx]
left_max = [[0, 0] for i in range(N+1)] # [value, idx]
for i, a in enumerate(A):
  left_max[i] = [a_max, idx]
  if a > a_max:
    a_max, idx = a, i

ans = [0] * (N+1)
next_i = C[0][1]
for _, i, _ in C: # indexだけ取得
  a, _, num = B[i] # 実体を取得、numは右側で同じ数になったとき、同じ山と見なして計算量削減
  if i == next_i:
    next_a, next_i = left_max[i] # 次の最大値であるnext_aになるまではこのiがsに追加される
    now_i = i
    ans[i] += (a - next_a) * num # 差分(a-next_a)をnum回分追加
    B[next_i][2] += num # 残った分はnext_iの石が消されるタイミングで消されるのでまとめる
  else:
    ans[now_i] += (a - next_a) * num
    B[next_i][2] += num

print(*ans[1:], sep='\n')

Submission status: Accepted

Solution code:
N = int(input())
A = [0] + list(map(int, input().split()))
B = [[a, i, 1] for i, a in enumerate(A)]
C = sorted(B, reverse=True)
a_max, idx = 0, 0 # [value, idx]
left_max = [[0, 0] for i in range(N+1)] # [value, idx]
for i, a in enumerate(A):
  left_max[i] = [a_max, idx]
  if a > a_max:
    a_max, idx = a, i

ans = [0] * (N+1)
next_i = C[0][1]
for _, i, _ in C:
  a, _, num = B[i]
  if i == next_i:
    next_a, next_i = left_max[i]
    now_i = i
    ans[i] += (a - next_a) * num
    B[next_i][2] += num
  else:
    ans[now_i] += (a - next_a) * num
    B[next_i][2] += num

print(*ans[1:], sep='\n')

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
a = LI()

asort = sorted(a)

d = defaultdict(int)
for i in range(N):
    d[a[i]] += 1
keys = sorted(list(d.keys()))

ans = [0]*N
max_ = 0
place = 0
for i in range(N):
    if a[i] > max_:
        diff = a[i]-max_
        num = N-bisect_left(asort,a[i])
        ans[i] = num*diff
        for j in range(place,len(keys)):
            if keys[j] <= max_:
                continue
            elif keys[j] >= a[i]:
                place = j
                break
            else:
                ans[i] += (keys[j]-max_)*d[keys[j]]
        max_ = a[i]

ans[0] = sum(a)-sum(ans[1:])

for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))

parent = [(0,-1)]
now = 0
for i,a in enumerate(A):
    if now < a:
        parent.append((a,i))
        now = a
A.sort()
ans = [0]*n
cnt = 0
p = parent[-1][1]
for a in A[::-1]:
    if parent[-1][0] >= a:
        p = parent[-1][1]
        ans[p] += cnt*(parent[-1][0] - parent[-2][0])
        parent.pop()
    if parent[-1][0] < a:
        cnt += 1
        ans[p] += a - parent[-1][0]
print('\n'.join(str(i) for i in ans))

Submission status: Accepted

Solution code:
N = int(input())
B = list(map(int, input().split()))
A = [(B[i], i) for i in range(N)]

A.sort(key = lambda x: x[0], reverse = True)

A.append((0, 0))

ans = [0] * N
tmp = N + 1
count = 1
for index, a in enumerate(A[:-1]):
    tmp = min(tmp, a[1])
    ans[tmp] += count * (a[0] - A[index + 1][0])
    count += 1

print (*ans, sep = '\n')

# print (A)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))

from collections import defaultdict
d = defaultdict(lambda: (n, 0))
for i, a in enumerate(A):
    min_id, cnt = d[a]
    d[a] = (min(min_id, i), cnt+1)

B = list(d.items())
B.sort()

#print(B)

ans = [0]*n
while True:
    a1, (m1, c1) = B.pop()
    if not B:
        ans[m1] += c1*a1
        break
    a2, (m2, c2) = B[-1]
    ans[m1] += c1*(a1-a2)
    B[-1] = (a2, (min(m1, m2), c1+c2))

print(*ans, sep='\n')

Submission status: Accepted

Solution code:
# 解説AC, add の部分を自分で作れなかった


def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    B = [(a, i+1) for i, a in enumerate(A)]
    B.sort(reverse=True)
    B.append((0, 0))
    ans = [0]*(N+1)
    idx = N+1
    for i in range(N):
        add = (i+1)*(B[i][0] - B[i+1][0])
        idx = min(idx, B[i][1])
        ans[idx] += add
    print(*ans[1:], sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import heapify, heappop

N = int(input())
A = list(map(int, input().split()))

que = [(-a, i + 1) for i, a in enumerate(A)]
heapify(que)

ans = [0] * (N + 1)
cnt = 0
while que:
    a, now = heappop(que)
    cnt += 1
    ans[now] = -a * cnt

    while que and que[0][1] > now:
        a, _ = heappop(que)
        ans[now] += -a
        cnt += 1

    if que:
        ans[now] -= -que[0][0] * cnt

print(*ans[1:], sep='\n')

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[[a[i],i] for i in range(n)]+[[0,n-1]]
b.sort(reverse=1)
ans=[0]*n
j=n-1
for i in range(n):
  j=min(b[i][1],j)
  c=b[i][0]-b[i+1][0]
  if c!=0:ans[j]+=c*(i+1)
print(*ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))

    target = [0]
    prev = a[0]
    for i in range(1, n):
        if a[i] > prev:
            target.append(i)
            prev = a[i]

    ax = [None] * n
    for i in range(n):
        ax[i] = [a[i], i]
    ax.sort(reverse=True)

    ans = [0] * n
    mult = 1
    for i in range(n-1):
        ans[target[-1]] += (ax[i][0] - ax[i+1][0]) * mult
        if (ax[i+1][0] < a[target[-1]] and ax[i+1][1] < target[-1]):
            target.pop()
        mult += 1
    ans[target[-1]] += ax[n-1][0] * mult

    for x in ans:
        print(x)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = [[int(i), j] for j, i in enumerate(input().split())]
a.sort(reverse=1)
a.append([0, n-1])
ans = [0] * n

j = n-1
for i in range(n):
    j = min(j, a[i][1])
    ans[j] += (i+1) * (a[i][0] - a[i + 1][0])
print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    nDict = dict()
    Atype = list(set(A))
    Atype.sort(reverse = True)
    Atype.append(0)
    for i, a in enumerate(A):
        if a in nDict: nDict[a].append(i)
        else: nDict[a] = [i]
    count = [0] * N
    minIndex = N
    group = 0
    for i in range(len(Atype) - 1):
        cN = Atype[i]
        minIndex = min(minIndex, nDict[cN][0])
        group += len(nDict[cN])
        nextN = Atype[i + 1]
        count[minIndex] += (cN - nextN) * group
    print("\n".join(map(str, count)))

    return 0

if __name__ == "__main__":
    solve()