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: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = LI()
A = [(L[i], i) for i in range(n)]
ans = [0] * n
A.sort()
min_ind = INF
for i in range(n - 1, 0, -1):
    min_ind = min(min_ind, A[i][1])
    if A[i - 1][0] < A[i][0]:
        ans[min_ind] += (A[i][0] - A[i - 1][0]) * (n - i)

ans[0] += A[0][0] * n
for j in ans:
    print(j)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
a = list(map(int, input().split()))
left = defaultdict(int)

for i in range(N-1, -1, -1):
    left[a[i]] = i

l = list(set(a))
l.sort(reverse=True)
ans = [0]*N
now = left[max(a)]
cnt = Counter(a)

for i in range(len(l)-1):
    ans[now] += (l[i]-l[i+1])*cnt[l[i]]
    cnt[l[i+1]] += cnt[l[i]]
    now = min(now, left[l[i+1]])

ans[now] += l[-1]*cnt[l[-1]]

for ans_i in ans:
    print(ans_i)

Submission status: Accepted

Solution code:
class BIT:
  def __init__(self, n):
    self.N = n+1
    self.bit = [0]*self.N
  
  def bit_sum(self, i):
    s = 0
    i += 1
    while i>0:
      s += self.bit[i]
      i -= i & -i
    return s

  def bit_add(self, i, n):
    i += 1
    while i<self.N:
      self.bit[i] += n
      i += i & -i

N, *A = map(int, open(0).read().split())
inf = [(a,i) for i, a in enumerate(A)]
n = A[0]
ls = [0]
for i in range(1,N):
  if A[i]>n:
    n = A[i]
    ls.append(i)
B = BIT(N)
C = BIT(N)
inf.sort(reverse=True)
cnt = [0]*N
ccnt = [0]*N
for a,i in inf:
  B.bit_add(i,a)
  cnt[i] = B.bit_sum(N-1)-B.bit_sum(i)
for a, i in inf:
  C.bit_add(i,1)
  ccnt[i] = C.bit_sum(N-1)-C.bit_sum(i)

ans = [0]*N
s = sum(A)
p = 0
x = 0
for i in range(len(ls)-1,0,-1):
  a = ls[i]
  b = ls[i-1]
  m = cnt[b]-A[b]*ccnt[b]
  n = m-x
  ans[a] = n
  s -= n
  x += ans[a]
ans[0] = s
print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
N = int(input())
L = [0] + list(map(int,input().split()))
D = {}
D[0] = [0,0]
for i in range(1,N+1):
    if L[i] not in D:
        D[L[i]] = [i,1]
    else:
        D[L[i]][1] += 1

A = list(D.items())
A.sort(reverse=True)
#print(A)

ans=0
ANS = [0 for i in range(N+1)]

for i in range(1,len(D)):
    ANS[A[i-1][1][0]] += (A[i-1][0] - A[i][0]) * A[i-1][1][1]
    A[i][1][0] = min(A[i-1][1][0],A[i][1][0])
    A[i][1][1] += A[i-1][1][1]

for i in range(1,len(ANS)):
    print(ANS[i])

Submission status: Accepted

Solution code:
def main():
    N,*A=map(int, open(0).read().split())
    L,C={},{}
    for i,a in enumerate(A):
        if a in C:
            C[a]+=1
        else:
            C[a]=1
            L[a]=i
    Z=[0]*N
    B=sorted(C,reverse=True)
    l=N-1
    cnt=0
    for b,c in zip(B,B[1:]+[0]):
        l=min(l,L[b])
        cnt+=C[b]
        Z[l]+=(b-c)*cnt
    print(*Z, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n = II()
    aa = LI()
    # できる数列にインデックスがかかれるときの最大値の底(bottom)
    bot = []
    mx = 0
    for i, a in enumerate(aa):
        if a > mx:
            bot.append((mx, i))
            mx = a
    #print(bot)
    aa.sort()
    ans = [0] * n
    j = n
    s = 0
    fin=0
    for mx, i in bot[::-1]:
        while j > 0 and aa[j - 1] > mx:
            j -= 1
            s += aa[j]
        ans[i]=s-(n-j)*mx-fin
        # print(mx,i,j,s,fin,ans)
        fin+=ans[i]
    print(*ans,sep="\n")

main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    ai = [(0, -1)] + [(a, i+1) for i, a in enumerate(A)]
    ai.sort()
    A = [a for a, i in ai]
    I = [i for a, i in ai]
    ans = [0] * (N+1)

    i = N
    same = 0
    q = []
    while i != 0:
        j = i
        while True:
            j -= 1
            if I[j] < I[i]:
                break
            heapq.heappush(q, A[j])
        d = A[i] - A[j]
        ans[I[i]] = d * (same+1)
        same += 1
        while q and q[0] >= A[j]:
            b = heapq.heappop(q)
            ans[I[i]] += b - A[j]
            same += 1
        i = j
    for r in ans[1:]:
        print(r)

def main():
    N = read_int()
    A = read_int_n()
    (slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

C = Counter(A)
# 重複削除して降順、この順に処理していく
unique = sorted(set(A), reverse=1) + [0]
# ある値が最初に出現するindexを保持
D = {}
for i in range(N-1, -1, -1):
    D[A[i]] = i

ans = [0] * N
prevcnt = 0
mnidx = INF
for i, a in enumerate(unique[:-1]):
    nxta = unique[i+1]
    # 今回の位置が選ばれる回数 = 次の値との差分 * 今の値の個数
    cnt = (a - nxta) * (C[a] + prevcnt)
    # 今の値の先頭index
    mnidx = min(mnidx, D[a])
    ans[mnidx] += cnt
    # 今回の個数を次回以降用に追加
    prevcnt += C[a]
[print(a) for a in ans]

Submission status: Accepted

Solution code:

"""

石の数が最大の内数字が大きいものから取り除いていくのが最適？

前にあるできるだけ数が多いものに譲っていく

優先度付きキューでaが大きい方からpopしていく？

numが現在より小さい→以降する
そうでない = 現在のnumよりは低いが次のnumよりは大きい
→次のnumが確定した瞬間に差分を計算して定常減少用に入れる

最後は残りを全部1に入れて終わり
"""
import heapq

N = int(input())

ans = [0] * N

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

q = []

for i,na in enumerate(a):

    heapq.heappush(q,[-1 * na , i])

nowa , nowi = heapq.heappop(q)
nowa *= -1
always = 0
tempq = [nowa]

for i in range(N-1):

    nexa , nexi = heapq.heappop(q)
    nexa *= -1

    if nexi > nowi:
        tempq.append(nexa)

    else:
        nowpl = always * (nowa - nexa)

        for j in tempq:
            nowpl += j - nexa

        always += len(tempq)
        tempq = [nexa]

        ans[nowi] += nowpl

        nowa = nexa
        nowi = nexi

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

print ("\n".join(map(str,ans)))

Submission status: Accepted

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

num=A[0]
data=[[A[0],0]]

for i in range(1,N):
    if A[i]>num:
        data.append([A[i],i])
        num=A[i]
        
B=sorted(A,reverse=True)
C=[0]*N
C[0]=B[0]
for i in range(1,N):
    C[i]=C[i-1]+B[i]
    
    
ans=[0]*N
cnt=0
kkk=0
for i in range(len(data)-1,0,-1):
    
    zzz=data[i-1][0]
    while kkk<N and B[kkk]>zzz:
        kkk+=1
    num=C[kkk-1]-kkk*zzz
    num-=cnt
    ans[data[i][1]]=num
    cnt+=num

ans[0]=sum(A)-sum(ans)

for u in ans:
    print(u)

Submission status: Accepted

Solution code:
#1は一意
#2は小さい番号の石の数が大きくなるように、大きい番号の石を除きたい

#個数が同順のものを、番号小以外が個数が時点になるまで除いてから、番号少を除く
n = int(input())
a = list(map(int, input().split( )))

cnt = {}#keyは個数、要素は最小番号

for i in range(n):
    if a[i] in cnt:
        cnt[a[i]][0] = min(cnt[a[i]][0],i)
        cnt[a[i]][1]+=1
    else:
        cnt[a[i]] = [i,1]

#個数、最小番号、番号の数    
mins = [[k,cnt[k][0],cnt[k][1]] for k in cnt]
mins.append([0,0,0])
#末端処理になっていない
mins.sort(reverse = True)
#print(mins)
ans = [0]*n

for i in range(len(mins)-1):
    k,cntk,l = mins[i][0],mins[i][1],mins[i][2]
    ans[cntk] += (k-mins[i+1][0])*l
    mins[i+1][2]+=l###=じゃおかしい
    if mins[i+1][1]>mins[i][1]:##追加
        mins[i+1][1] = mins[i][1]
#ans[mins[-1][1]]=n*mins[-1][0]

for ai in ans:
    print(ai)

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)
c = dd(int)
for i in range(N - 1, -1, -1):
  d[a[i]] = i
  c[a[i]] += 1
c[0] = 0
ks = sorted(d.keys())
res = [0] * N
for i in range(len(ks) - 1, 0, -1):
  x = ks[i]
  y = ks[i - 1]
  c[y] += c[x]
  d[y] = min(d[y], d[x])
for i in range(len(ks)):
  x = ks[i]
  y = 0
  if i > 0: y = ks[i - 1]
  res[d[x]] += c[x] * (x - y)
for r in res: print(r)

Submission status: Accepted

Solution code:
from bisect import bisect_right, bisect_left
inpl = lambda: list(map(int,input().split()))
N = int(input())
A = inpl()
x = [-1]
y = [0]
for i in range(N):
    if A[i] > y[-1]:
        x.append(i)
        y.append(A[i])
ans = [0] * N
L = len(x)
k = [0] * (L+1)
i = N-1
base = y[-1]
for n in range(L-1,0,-1):
    roof = base
    base = y[n-1]
    height = roof - base
    k[n] += k[n+1]
    ans[x[n]] += k[n] * height
    while i >= x[n]:
        p = bisect_left(y, A[i])
        ans[x[p]] += A[i] - y[p-1]
        k[p-1] += 1
        i -= 1
for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
import collections
import heapq
n=int(input())
A=[int(i) for i in input().split()]
Ans=[0]*n
M=[0]#自分より前の最大値をメモ。これ以下だと現れない
for i in range(n):
  M.append(max(M[-1],A[i]))
D=collections.defaultdict(int)
H=[]
for i in range(n):
  j=n-1-i
  if A[j]<=M[j]:
    heapq.heappush(H,-A[j])#出現しないインデックスの数を管理。大きいほうから取り出す。
  else:
    Ans[j]=(A[j]-M[j])*(D[A[j]]+1)#自分より前の最大値と自分の差かける自分自身と同じ数のこれまでの出現回数
    D[M[j]]+=D[A[j]]+1#自分自身より後ろの自分と同じ数全てを自分より前の最大値まで減らすことで増える分
    ct=0
    while H:#自分より後ろで自分より小さいが、自分の前の最大値より大きいものを全て見る
      a=heapq.heappop(H)
      a=-a
      if a<=M[j]:
        heapq.heappush(H,-a)
        break
      else:
        Ans[j]+=a-M[j]
        D[M[j]]+=1

for a in Ans:
  print(a)

Submission status: Accepted

Solution code:
import collections
import heapq
n=int(input())
A=[int(i) for i in input().split()]
Ans=[0]*n
M=[0]
for i in range(n):
  M.append(max(M[-1],A[i]))
D=collections.defaultdict(int)
H=[]
for i in range(n):
  j=n-1-i
  if A[j]<=M[j]:
    heapq.heappush(H,-A[j])
  else:
    Ans[j]=(A[j]-M[j])*(D[A[j]]+1)
    D[M[j]]+=D[A[j]]+1
    ct=0
    while H:
      a=heapq.heappop(H)
      a=-a
      if a<=M[j]:
        heapq.heappush(H,-a)
        break
      else:
        Ans[j]+=a-M[j]
        D[M[j]]+=1

for a in Ans:
  print(a)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = list(range(n))
s = list(map(list,zip(a,b)))
s.sort(reverse=True)
s.append([0,0])
ans = [0]*n
for i in range(n):
  dif = s[i][0]-s[i+1][0]
  ans[s[i][1]] += dif*(i+1)
  if s[i+1][1]>s[i][1]:
    s[i+1][1] = s[i][1]
print(*ans,sep="\n")

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = [(x,i) for i,x in enumerate(a)]
l.sort(reverse=True)
l += [(0,n)]
g = [0]*n
m = n
for i in range(n):
  s = l[i][1]
  if m > s: m = s
  g[m] += (l[i][0]-l[i+1][0])*(i+1)
for x in g: print(x)

Submission status: Accepted

Solution code:
def examC():
    N, M = LI()
    if N-M//2>=0:
        ans = M//2
    else:
        ans = N + (M-N*2)//4
    print(ans)
    return

def examD():
    N = I()
    S = SI()
    for i1,i2 in [[0,0],[0,1],[1,0],[1,1]]:
        flag = True
        sheep = [1]*N
        sheep[0] = i1
        sheep[1] = i2
        for j in range(1,N-1):
            if S[j]=="o":
                cur = 1
            else:
                cur = 0
            sheep[j+1] = (sheep[j]^cur)^sheep[j-1]
        if S[-1] == "o":
            cur = 1
        else:
            cur = 0
        if sheep[0]!=(sheep[-1] ^ cur) ^ sheep[-2]:
            flag = False
        if S[0] == "o":
            cur = 1
        else:
            cur = 0
        if sheep[1]!=(sheep[0] ^ cur) ^ sheep[-1]:
            flag = False
        if flag:
            ans = ""
            for i in sheep:
                if i==1:
                    ans += "S"
                else:
                    ans += "W"
            print(ans)
            return
    print(-1)
    return

def examE():
    N = I()
    A = LI()
    Ai = [[0,0]]
    for i in range(N):
        Ai.append([A[i],i])
    Ai = sorted(Ai, key=lambda x:x[1], reverse = True)
    Ai = sorted(Ai, key=lambda x:x[0], reverse = True)
#    print(Ai)
    ans = [0]*N
    now = N
    for i in range(N):
        now = min(now,Ai[i][1])
        ans[now] += (i+1)*(Ai[i][0]-Ai[i+1][0])
    for v in ans:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examE()

"""

"""

Submission status: Accepted

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

from collections import defaultdict
G = defaultdict(list)
D = {}

for i in range(N):
    tmp = A[i]
    G[tmp].append(i)
    
keylist = []

for key in G:
    G[key].sort()
    D[key] = len(G[key])
    keylist.append(key)

keylist.sort()
keylist = keylist[::-1]
keylist.append(0)

D[0] = 0
G[0].append(0)

ans = [0]*N

for i in range(len(keylist)-1):
    key = keylist[i]
    nextkey = keylist[i+1]
    tmpi = G[key][0]
    ans[tmpi] += D[key]*(key-nextkey)
    
    D[nextkey] += D[key]
    G[nextkey][0] = min(G[nextkey][0],tmpi)
    
for i in ans:
    print(i)

Submission status: Accepted

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

S = sum(A)
for i in range(N):
    A[i] = [A[i], i+1]

A.sort(reverse=True)
ans = [0]*(N+1)
i = 0
num = N+1
while i < N-1:
    num = min(num, A[i][1])
    while i < N-1 and A[i][0] == A[i+1][0]:
        num = min(num, A[i+1][1])
        i += 1
    if i == N-1:
        break
    ans[num] += (i+1)*(A[i][0]-A[i+1][0])
    i += 1

ans[1] += S-sum(ans)
for i in range(1, N+1):
    print(ans[i])

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

Bs = [0]
xs = [-1]
for i, A in enumerate(As):
    if Bs[-1] < A:
        Bs.append(A)
        xs.append(i)

lenB = len(Bs)
sumAs = [0] * lenB
numFulls = [0] * lenB
for A in As:
    i = bisect_left(Bs, A)
    sumAs[i] += A - Bs[i-1]
    numFulls[i-1] += 1

for i in reversed(range(lenB-1)):
    numFulls[i] += numFulls[i+1]

anss = [0] * N
for i in range(1, lenB):
    ans = sumAs[i]
    ans += (Bs[i]-Bs[i-1]) * numFulls[i]
    anss[xs[i]] = ans

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
l = []
ans = [0 for i in range(n)]
for i in range(n):
    l.append([a[i],i])
l.sort(key=lambda x:x[1],reverse=True)
l.sort(key=lambda x:x[0],reverse=True)
count = 1
count0 = 0
b = l[0][0]
c = l[0][1]
for i in range(1,n):
    if l[i][0] == b:
        count += 1
        c = min(c,l[i][1])
    else:
        ans[c] += (b-l[i][0])*count
        count += 1
        b = l[i][0]
        c = min(l[i][1],c)
ans[c] += b*count
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    AI=[(a,i) for i,a in enumerate(map(int,input().split()))]
    AI.append((0,-1))
    AI.sort(reverse=1)

    m=INF
    ans=[0]*n
    for i in range(n):
        d=AI[i][0]-AI[i+1][0]
        m=min(m,AI[i][1])
        ans[m]+=(i+1)*d

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

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    a=list(map(int,input().split()))
    d={0:[-1]}
    for j,i in enumerate(a):
        if i in d.keys():d[i].append(j)
        else:d[i]=[j]
    d=sorted([[i,min(j),len(j)] for i,j in d.items()],reverse=True)
    ans=[0]*n
    l=0
    m=n
    for k in range(len(d)-1):
        x,y,z=d[k]
        l+=z
        m=min(m,y)
        ans[m]+=(x-d[k+1][0])*l
    for i in ans:
        print(i)
main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
D = []
for id,a in enumerate(A):
  D.append([a,id])
D = sorted(D)[::-1]
D.append([0,0])
#Cumsum = [0]
#for i in D[::-1]:
#  Cumsum.append(i[0]+Cumsum[-1])
#Cumsum = Cumsum[::-1]
#print(Cumsum)
cnt = [0] * N
minid = D[0][1]
for i in range(N):
  d = D[i][0] - D[i+1][0]
  cnt[minid] += d * (i + 1)
  if D[i+1][1] < minid:
    minid = D[i+1][1]
for i in range(N):
  print(cnt[i])

Submission status: Accepted

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

a = list(zip(a, range(len(a))))
a = sorted(a, reverse = True) + [(0, 0)]

ans = [0] * n
min_ind = 10**9

for i in range(n):
    tmp = a[i][0] - a[i+1][0]
    min_ind = min(min_ind, a[i][1])
    ans[min_ind] += (i+1) * tmp

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left

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

dics = []
q = []
Ind = []
ans = [0]*N

for i, a in enumerate(A):
    ia = bisect_left(q, a)
    if ia == len(q):
        Ind.append(i)
        q.append(a)
        dics.append({a:1})
    else:
        dic = dics[ia]
        if not a in dic.keys():
            dic[a] = 1
        else:
            dic[a] += 1

L = len(q)
for l in reversed(range(L)):
    if l == 0:
        for k, v in dics[0].items():
            ans[Ind[0]] += k*v
    else:
        bef = q[l-1]
        for k, v in dics[l].items():
            ans[Ind[l]] += (k-bef)*v
            dics[l-1][bef] += v

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
a = [int(i) for i in input().split()]

b = defaultdict(lambda : [float('inf'), 0])
for i in range(N) :
    b[a[i]][0] = min(b[a[i]][0], i)
    b[a[i]][1] += 1

# [value, first_appearance, count]
c = [(0, 0, 0)]
for k, v in b.items() :
    c.append((k, v[0], v[1]))
c.sort()

ret = [0] * N
pre_v, pre_i, pre_c = c.pop()
while c :
    cur_v, cur_i, cur_c = c.pop()
    ret[pre_i] += (pre_v - cur_v) * pre_c
    cur_c += pre_c
    pre_v, pre_i, pre_c = cur_v, min(pre_i, cur_i), cur_c
    
for r in ret :
    print(r)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

def main():
    n = int(input())
    a = [(i, _a) for i, _a in enumerate(map(int, input().split()))]
    a.append((n, 0))
    ans = [0 for _ in range(n)]
    a = list(sorted(a, key=lambda x: (-x[1], x[0])))
    mini = a[0][0]
    for j, _a in enumerate(a):
        if j>0 and a[j-1][1] != _a[1]:
            ans[mini] += (a[j-1][1] - _a[1]) * j
            mini = min(mini, a[j][0])
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
e=enumerate
n,a=open(0)
a=sorted((int(i),j)for j,i in e(('0 '+a).split()))[::-1]
c=[0]*int(n)
t=10**18
for k,(i,j)in e(a[:-1],1):
  t=min(t,j)
  c[t-1]+=(i-a[k][0])*k
print(*c)

Submission status: Accepted

Solution code:
N = int(input())
A = [(a, i) for i, a in enumerate(map(int, input().split()))]
A.sort(reverse=True)
A.append((0, 0))

ans = [0] * N
now = float('inf')

for j, (a, i) in enumerate(A[:N], start=1):
    now = min(now, i)
    ans[now] += j * (a - A[j][0])

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
a = [0] + list(map(int, input().split()))
p = sorted((-a[i], -i) for i in range(n + 1))
ans = [0] * (n + 1)
m = n
for i in range(n):
    k, v = -p[i][1], -p[i][0]
    nv = -p[i + 1][0]
    m = min(m, k)
    ans[m] += (i + 1) * (v - nv)
print(*ans[1:], sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


def main():
    n = int(input())
    a = list(map(int, input().split()))
    ai = [(0, 0)]
    for i, _a in enumerate(a):
        ai.append((_a, i+1))
    ai.sort(key=lambda x: (-x[0], x[1]))
    ans = [0 for _ in range(n)]
    mini = ai[0][1]
    for i in range(n):
        if mini > ai[i][1]:
            mini = ai[i][1]
        ans[mini-1] += (i+1) * (ai[i][0] - ai[i+1][0])
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys,bisect
    input = sys.stdin.readline

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

    b = [0] + sorted(a)

    res = [0]*n

    d = dict()
    for i in range(n):
        if not a[i] in d:
            d[a[i]] = i

    p = n
    while p > 0:
        k = bisect.bisect_left(b,b[p])
        res[d[b[k]]] += (n+1-k)*(b[k]-b[k-1])
        if k -1 >= 1:
            d[b[k-1]] = min(d[b[k]],d[b[k-1]])
        p = k-1
    for e in res:
        print(e)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions

import sys
def input():
	return sys.stdin.readline().strip()

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

top_list = [0]


for i in range(1, N):

	if a[i] > a[top_list[-1]]:
		top_list.append(i)

num_list = [0]*N
com = []
for i in range(len(top_list)):
	com.append(a[top_list[i]])
com.sort()

for i in range(N - 1, top_list[-1], -1):
	com.append(a[i])
com.sort()

stock = 0
#print(com, top_list, num_list)
for top in range(len(top_list) - 2, -1, -1):
	if top_list[top + 1] - top_list[top] > 10000:
		for i in range(top_list[top + 1] - 1, top_list[top], -1):
			#bisect.insort(com, a[i])
			com.append(a[i])
		com.sort()
	else:
		for i in range(top_list[top + 1] - 1, top_list[top], -1):
			bisect.insort(com, a[i])

	judge = 0
	total = stock*(a[top_list[top + 1]] - a[top_list[top]])
	#print(total, (a[top_list[top + 1]] - a[top_list[top]])*stock,  top)
	while judge == 0:
		x = com.pop()
		if x > a[top_list[top]]:
			total += x - a[top_list[top]]
			stock += 1
		else:
			bisect.insort(com, x)
			judge = 1
	num_list[top_list[top + 1]] = total
	#print(com, top_list, num_list, stock)


num_list[top_list[0]] = sum(a) - sum(num_list)
for i in range(N):
	print(num_list[i])

Submission status: Accepted

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

# 現在末尾に追加される山より若い山で，最も個数の大きいものが次の山になる
# 他の山を次の山の個数以下まで減らす

ans = [0] * N

numList = [(a, i) for i, a in enumerate(A)]
numList.sort(reverse=True)
numList.append((0, 0))

y = float('inf')
for c, (a, i) in enumerate(numList[: N], start=1):
    y = min(y, i)
    ans[y] += c * (a - numList[c][0])

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

Submission status: Accepted

Solution code:
import bisect

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

big_list = []
num_list = []
biggest = 0
for i, a_i in enumerate(a):
    if a_i > biggest:
        big_list.append(a_i)
        num_list.append(i)
        biggest = a_i
big_list.append(10 ** 10)
big_list.append(0)
num_list.append(0)
num_list.append(0)

ans = [0] * N
a.sort()
j = 0
for i, a_i in enumerate(a):
    if a_i < big_list[j]:
        ans[num_list[j]] += a_i - big_list[j - 1]
    else:
        ans[num_list[j]] += (big_list[j] - big_list[j - 1]) * (N - i)
        j += 1
for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
#!/usr/bin/python3.6
n = int(input())
a = [int(item) for item in input().split()]
awid = []
for i, item in enumerate(a):
    awid.append((item, i))
awid.sort(reverse=True)

bit = [0] * (n + 1) 
cnt = [0] * (n + 1) 
# Add w to ax 
def bit_add(bit, x, w):
    while x <= n:
        bit[x] += w
        x += x & -x

# Sum a1 to ax 
def bit_sum(bit, x):
    ret = 0
    while x > 0:
        ret += bit[x]
        x -= x & -x
    return ret

min_as = [-1] * n
min_a = 0
for i, item in enumerate(a):
    if item > min_a:
        min_as[i] = min_a
        min_a = item

ans = [0] * n
itr = 0
subbed = 0
for i, item in enumerate(min_as[::-1]):
    place = n - 1 - i
    if item != -1:
        while itr < n and awid[itr][0] > item:
            val, index = awid[itr]
            bit_add(bit, index + 1, val)
            bit_add(cnt, index + 1, 1)
            itr += 1
        ret = bit_sum(bit, n) - bit_sum(bit, place) - (bit_sum(cnt, n) - bit_sum(cnt, place)) * item - subbed
        ans[place] = ret
        subbed += ret
for item in ans:
    print(item)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
D = []
for i in range(N):
    D.append((a[i], i))
D.append((0, -1))
D.sort(reverse=True)
ans = [0] * N
mi = float('inf')
for i in range(N):
    mi = min(mi, D[i][1])
    ans[mi] += (D[i][0] - D[i + 1][0]) * (i + 1)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

XY = [(a, i) for i, a in enumerate(A)]
XY.sort(reverse=True)

# 解説
ans = [0] * N
min_y = IINF
for i, (x, y) in enumerate(XY):
    min_y = min(min_y, y)
    x2 = XY[i + 1][0] if i + 1 < N else 0
    ans[min_y] += (x - x2) * (i + 1)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        0 番目から i 番目までの合計
        :param int i:
        :return:
        """
        ret = 0
        x = i + 1
        while x > 0:
            ret += self._bit[x - 1]
            x -= x & -x
        return ret

    def __len__(self):
        return self._size


N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
A = np.array(A, dtype=int)
ans = np.zeros(N, dtype=int)

# for i in range(N):
#     if A[i] <= 0:
#         continue
#     ans[i] = np.minimum(A, A[i]).sum()
#     A = np.maximum(0, A - A[i])
# print(ans)

counts = Counter(A)
counts[0] = 0
counts[IINF] = 0
keys = list(sorted(counts.keys()))

ki = 0
cnt = 0
s = 0
for i in range(N):
    if A[i] - s <= 0:
        continue
    m = A[i]
    # s 以上 m 以下のやつの合計
    p = s
    while keys[ki] <= m:
        ans[i] += (keys[ki] - p) * (N - cnt)
        p = keys[ki]
        cnt += counts[keys[ki]]
        ki += 1

    s = A[i]

print(*ans, sep='\n')
# [10  7  0  4  0  3  0  2  3  0]

Submission status: Accepted

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

for i in range(n):
    a[i] = [a[i],i]

a.sort()
a.reverse()
a.append([0,-1])

b = [0]*n
c = float('inf')

for i in range(n):
    c = min(c,a[i][1])
    b[c] += (a[i][0]-a[i+1][0])*(i+1)

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