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:
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]

n=I()
a=LI()

d={}
nd={}
for i,x in enumerate(a):
    if x in d:
        d[x]=min(i,d[x])
        nd[x]+=1
    else:
        d[x]=i
        nd[x]=1

A=sorted([i for i in d.items()],key=lambda x:x[0])
ans=[0]*n
px,pm=A.pop()
nn=nd[px]
while A:
    x,m=A.pop()
    ans[pm]+=(px-x)*nn
    nn+=nd[x]
    px,pm=x,min(m,pm)
ans[0]+=sum(a)-sum(ans)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7

n=I()
a=LI()

d={}
nd={}
for i,x in enumerate(a):
    if x in d:
        d[x]=min(i,d[x])
        nd[x]+=1
    else:
        d[x]=i
        nd[x]=1

A=[i for i in d.items()]
A=sorted(A,key=lambda x:x[0])
#[::-1]
ans=[0]*n
px,pm=A.pop()
nn=nd[px]
while A:
    x,m=A.pop()
    ans[pm]+=(px-x)*nn
    nn+=nd[x]
    px,pm=x,min(m,pm)
ans[0]+=sum(a)-sum(ans)
#print(n,sum(a),a)
#print(*ans)
for i in ans:print(i)

Submission status: Accepted

Solution code:
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 status: Accepted

Solution code:
from operator import itemgetter
import sys
N=int(input())
A=[int(i) for i in input().split()]
B=[(A[i],i) for i in range(N)]
B=sorted(B,key=itemgetter(1))
B=sorted(B,key=itemgetter(0))
T=[0]*N
cos,pt=B.pop()
for i in range(1,N):
    cos2,pt2=B.pop()
    T[pt]+=(cos-cos2)*i
    pt=min(pt,pt2)
    cos=cos2
T[pt]+=cos*N
for i in T:
    print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
class BIT():
    def __init__(self, number):
        self.n = number
        self.list = [0] * (number + 1)

    def add(self, i, x):  # ith added x  1indexed
        while i <= self.n:
            self.list[i] += x
            i += i & -i

    def search(self, i):  # 1-i sum
        s = 0
        while i > 0:
            s += self.list[i]
            i -= i & -i
        return s

    def suma(self, i, j):  # i,i+1,..j sum
        return self.search(j) - self.search(i - 1)

N=int(input())
A=[int(i) for i in input().split()]
C=sorted(set(A))
ndd=defaultdict(int)
for i in range(len(C)):
    ndd[i+1]=C[i]
dd=defaultdict(int)
for i in range(len(C)):
    dd[C[i]]=i+1
#print(ndd,dd)
visit=[0]*N
visit[0]=1
s=A[0]
H=[]
H.append(s)
for i in range(1,N):
    if s<A[i]:
        s=A[i]
        H.append(s)
        visit[i]=1

BITI=BIT(N+1)
BITI2=BIT(N+1)
j=len(H)-1
l=dd[H[j]]
num=sum(A)
T=[0]*N
ans=0
for i in range(N-1,-1,-1):
    if l==dd[A[0]]:
        break
    BITI.add(dd[A[i]],A[i])
    BITI2.add(dd[A[i]],1)
    if dd[A[i]]==l and visit[i]==1:
        T[i]=BITI.suma(dd[H[j-1]],N+1)-BITI2.suma(dd[H[j-1]],N+1)*H[j-1]-ans
        ans+=T[i]
        #print(i,j,l,T[i],ans)
        j-=1
        l=dd[H[j]]
x=num-sum(T)
T[0]=x
#print(visit,T)
for t in T:
    print(t)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
b = []
for i in range(N):
    b.append([a[i], i+1])
b.sort(reverse = True)
ans = [0]*(N+1)
mini = N+1

for i in range(N-1):
    mini = min(mini, b[i][1])
    if b[i+1][0] - b[i][0] < 0:
        ans[mini] += (b[i][0] - b[i+1][0])*(i+1)

ans[1] += N*b[-1][0]
for i in range(N):
    print(ans[i+1])

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = sorted(list(set(a)))
a_to_i = dict()
for i in range(len(b)):
	a_to_i[b[i]] = i

a_count = [0 for _ in range(len(b))]
for x in a:
	a_count[a_to_i[x]] += 1

cum_reversed = [a_count[-1]]
for i in range(len(b)-2, -1, -1):
	cum_reversed.append(cum_reversed[-1] + a_count[i])

dominant = [-1 for _ in range(len(b))]
i = 0
for j in range(n):
	if i == len(b):
		break
	while a[j] >= b[i]:
		dominant[i] = j
		i += 1
		if i == len(b):
			break
b.reverse()
b.append(0)
dominant.reverse()

ans = [0 for _ in range(n)]

for i in range(len(b)-1):
	ans[dominant[i]] += (b[i] - b[i+1]) * cum_reversed[i]

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

Submission status: Accepted

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


def solve(n, a):

    ans = [0] * n

    q = []
    for i in range(n):
        ai = a[i]
        heapq.heappush(q, (-ai, i))

    ap, p = heapq.heappop(q)
    ap = -ap
    c = 0
    cnt = 1
    while len(q):
        ai, i = heapq.heappop(q)
        ai = -ai
        if p < i:
            c -= ap - ai
            cnt += 1
        else:
            ans[p] = c + (ap - ai) * cnt
            cnt += 1
            p = i
            ap = ai
            c = 0

    ans[p] = c + ap * cnt

    for c in ans:
        print(c)


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

    solve(n, a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
def inpl(): return list(map(int, input().split()))

N = int(input())
A = inpl()
X = sorted([(a, i) for i, a in enumerate(A, start=1)], key=lambda x: [x[0], -x[1]])
answer = [0]*(N+1)
a, i = X.pop()

for c in range(1, N):
    b, j = X.pop()
    answer[i] += (a-b)*c
    i = min(i, j)
    a = b
answer[i] += a * N

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

Submission status: Accepted

Solution code:
N=int(input())
A=[(int(a),i) for i,a in enumerate(input().split())]
A.append((0,float("inf")))
A.sort()
k=A[-1][1]
ans=[0]*N
for i in range(N)[::-1]:
  ans[k]+=(A[i+1][0]-A[i][0])*(N-i)
  k=min(k,A[i][1])
for i in range(N):
  print(ans[i])

Submission status: Accepted

Solution code:
import itertools, bisect
def inpl(): return [int(i) for i in input().split()]

N = int(input())
a = inpl()
sa = sorted(a)
acsa = list(itertools.accumulate(sa)) + [0]
acans = 0
ma = 0
ans = [0]*N
for i in range(N):
    if ma >= a[i]:
        continue
    ma = a[i]
    x = bisect.bisect_left(sa, a[i]) - 1
    ans[i] = a[i]*(N-1-x) + acsa[x] - acans
    acans += ans[i]
    
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
As = sorted(A)
cumax = [0]*N
ma = 0
for i, a in enumerate(A):
    cumax[i] = max(cumax[i-1], a)

ias = 0
pma = 0
ofs = 0
for i, a in enumerate(cumax):
    if a == pma:
        print(0)
        continue
    s = 0
    while ias < N and As[ias] <= a:
        s += As[ias] - ofs
        ias += 1
    s += (N-ias)*(a-ofs)
    pma = a
    ofs = a
    print(s)

Submission status: Accepted

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

# (ai, i)で降順ソート
A = sorted([(ai, i) for i, ai in enumerate(A, start=1)], reverse=True)

# 便宜上N+1番目として(0, 0)を持っておく
A.append((0, 0))

# 計算
ans = [0] * (N + 1)
y = []
for i in range(N):
    heapq.heappush(y, A[i][1])
    ans[y[0]] += (i + 1) * (A[i][0] - A[i + 1][0])

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

Submission status: Accepted

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

ans = [0]*n

b = []

for i, x in enumerate(a):
    b.append([-x, i])

b.sort()

c = []
p = b[0]
x = [-b[0][0], b[0][1], 1]
for i in range(1, n):
    if -b[i][0] == x[0]:
        x[2] = i+1
    else:
        c.append(x)
        x = [-b[i][0], b[i][1], i+1]
c.append(x)

s = 0
t = c[0][1]
for i in range(len(c)-1):
    x = (c[i][0]-c[i+1][0])*c[i][2]
    t = min(t, c[i][1])
    ans[t] += x
    s += x
ans[min(t, c[-1][1])] += sum(a)-s

for x in ans:
    print(x)

Submission status: Accepted

Solution code:
from functools import cmp_to_key

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

def group(a):
    d = {}
    for i, x in enumerate(a):
        d.setdefault(x, []).append(i)
    return list(map(
        lambda x: [x[0], x[1][0], len(x[1])],
        sorted(d.items(), key=cmp_to_key(lambda x, y: x[0] - y[0]), reverse=True)
    ))

ans = [0] * n
g = group(a)
g.append([0, 0, 0])
for c, n in zip(g[:-1], g[1:]):
    ans[c[1]] += (c[0] - n[0]) * c[2]
    n[1] = min(c[1], n[1])
    n[2] += c[2]

[print(a) for a in ans]

Submission status: Accepted

Solution code:
N = int(input())
A = map(int, input().split())
S = sorted([[a, i] for i, a in enumerate(A)], key=lambda x: x[0], reverse=True)
S.append([0, N])
B = [0 for i in range(N)]
num = S[0][1]
for i in range(1, N + 1):
  if S[i - 1][0] > S[i][0]:
   B[num] += (S[i - 1][0] - S[i][0]) * i
  num = min(num, S[i][1])
for b in B:
  print(b)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
S = list(map(int,input().split()))
T = []
for i in range(N):
    T.append((i,S[i]))
U = sorted(T,key=lambda x:x[1], reverse=True)

Ans = [0]*N
c,v = 0,10**10

for i in range(N-1):
    c+=1
    v = min(v,U[i][0])
    if U[i][1]==U[i+1][1]:
        continue
    else:
        Ans[v] += (U[i][1] - U[i+1][1])*c
else:
    Ans[0] = 0
    Ans[0] = sum(S) - sum(Ans)

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

dic = defaultdict(lambda:(N,0))
for i,a in enumerate(src):
    m,n = dic[a]
    dic[a] = (min(m,i), n+1)
order = sorted(list(dic.items()))

hist = [0] * N
while True:
    a1, (m1, n1) = order.pop()
    if not order:
        hist[m1] += n1 * a1
        break
    a2, (m2, n2) = order[-1]
    hist[m1] += n1 * (a1-a2)
    order[-1] = (a2, (min(m1,m2), n1+n2))

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

Submission status: Accepted

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

key = lis[0]
num = [0]
li = [key]
for i in range(1,n):
	if lis[i] > key:
		key = lis[i]
		num.append(i)
		li.append(key)

m = len(li)
nu = [li[0]]+[li[i+1]-li[i] for i in range(m-1)]

he = [0]*m
cou = [0]*m

from bisect import bisect_left

for k in lis:
	sen = bisect_left(li,k)
	cou[sen] += k -li[sen]
	he[sen] += 1

key = 0
for i in reversed(range(m)):
	key += he[i]
	he[i] = key

for i in range(m):
	cou[i] += he[i]*nu[i]

ans = [0]*n
for i,c in zip(num,cou):
	ans[i] = c

for r in ans:
	print(r)

Submission status: Accepted

Solution code:
N = int(raw_input())
V = map(int, raw_input().split(' '))

sorted_V = [N-i-1 for i in range(N)]

sorted_V.sort(reverse=True,key=lambda x: V[x])
lowest = N

uses = [0 for i in range(N)]

last = V[sorted_V[0]]

for ind, val in enumerate(sorted_V):
	if ind != N - 1 and V[sorted_V[ind]] == V[sorted_V[ind + 1]]:
		continue

	lowest = min(lowest, val)
	spots = ind + 1

	if ind == N - 1:
		individual_removals = last
		last = 0
	else:
		individual_removals = last - V[sorted_V[ind + 1]]
		last = V[sorted_V[ind + 1]]

	full_removals = individual_removals * spots
	uses[lowest] += full_removals

for i in uses:
	print i

Submission status: Accepted

Solution code:
from collections import defaultdict

n=int(raw_input())
a=map(int,raw_input().split())
check=[]
d=defaultdict(int)
li=set([])
now=0
for i in xrange(n):
    if now<a[i]:
        now=a[i]
        check.append(i)
    d[a[i]]+=1
    li.add(a[i])
li=sorted(list(li))
b=[0]*(n+5)
i=0
idx=dict()
for key in li:
    b[i]=d[key]
    idx[key]=i
    i+=1
ans=[0]*(n+1)
for i in xrange(len(check)-2,-1,-1):
    cnt=0
    for j in xrange(idx[a[check[i]]]+1,idx[a[check[i+1]]]+1):
        ans[check[i+1]]+=b[j]*(li[j]-a[check[i]])
        cnt+=b[j]
    b[idx[a[check[i]]]]+=cnt
for i in xrange(1,n):
    if a[0]<a[i]:
        a[i]=a[0]
ans[0]=sum(a)
for i in xrange(n):
    print ans[i]

Submission status: Accepted

Solution code:
from collections import defaultdict
class BIT():
    def __init__(self,size):
        self.size=size
        self.node=[0]*(size+1)

    def sum(self,idx):
        ret=0
        while idx>0:
            ret+=self.node[idx]
            idx-=idx&(-idx)
        return ret

    def add(self,idx,x):
        while idx<=self.size:
            self.node[idx]+=x
            idx+=idx&(-idx)

n=int(raw_input())
a=map(int,raw_input().split())
check=[]
d=defaultdict(int)
li=set([])
now=0
for i in xrange(n):
    if now<a[i]:
        now=a[i]
        check.append(i)
    d[a[i]]+=1
    li.add(a[i])
li=sorted(list(li))
b=[0]*(n+5)
i=0
idx=dict()
for key in li:
    b[i]=d[key]
    idx[key]=i
    i+=1
ans=[0]*(n+1)
for i in xrange(len(check)-2,-1,-1):
    cnt=0
    for j in xrange(idx[a[check[i]]]+1,idx[a[check[i+1]]]+1):
        ans[check[i+1]]+=b[j]*(li[j]-a[check[i]])
        cnt+=b[j]
    b[idx[a[check[i]]]]+=cnt
for i in xrange(1,n):
    if a[0]<a[i]:
        a[i]=a[0]
ans[0]=sum(a)
for i in xrange(n):
    print ans[i]

Submission status: Accepted

Solution code:
n = int(input())
an = list(map(int, input().split()))
sa = sorted(((a, i) for i, a in enumerate(an)), reverse=True)
sa.append((0, 0))

result = [0] * n
prev_a, min_i = sa[0]
for j, (a, i) in enumerate(sa[1:]):
    result[min_i] += (j + 1) * (prev_a - a)
    min_i = min(min_i, i)
    prev_a = a

for cnt in result:
    print(cnt)

Submission status: Accepted

Solution code:
# coding: utf-8

n_mou = int(input())
l_mou = list(map(int, input().split()))
l_mou_ind = [[l_mou[i], i] for i in range(n_mou)]
l_mou_ind.sort()

l_ans = [0 for i in range(n_mou)]

l_ans[0] = l_mou_ind[0][0] * n_mou
min_index = l_mou_ind[-1][1]
for i in range(n_mou - 1, 0, -1):
    min_index = min(min_index, l_mou_ind[i][1])
    if l_mou_ind[i - 1][0] != l_mou_ind[i][0]:
        l_ans[min_index] += (l_mou_ind[i][0] - l_mou_ind[i - 1][0]) * (n_mou - i)

for i in range(n_mou):
    print(l_ans[i])

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
n = int(raw_input())
a = [[int(k),i+1] for i,k in enumerate(raw_input().split())]
a.sort(reverse=True)
z = [l[1] for l in a]
s=[0]*n
a.append([0,0])
min_a_i = float('inf')
for i,p in enumerate(a[:-1]):
    min_a_i = min(min_a_i, a[i][1])
    if not p[0] == a[i+1][0]:
        q = p[0] - a[i+1][0]
        s[min_a_i-1] += (i+1)*q

for t in s:
    print(t)

Submission status: Accepted

Solution code:
def binary_search(item, values):
  top = 0
  bottom = len(values) - 1
  length = bottom - top + 1
  middle = top + (length // 2)
  while length >= 1:
    middle_item = values[middle][1]
    if middle_item == item:
      break
    if middle_item < item:
      top = middle + 1
    else:
      bottom = middle - 1
    length = bottom - top + 1
    middle = top + (length // 2)
  if middle <= (len(values) - 1):
    return middle
  else:
    return -1

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

limits = [(-1, 0)]
from collections import defaultdict
counter = defaultdict(int)
gaps = defaultdict(int)
for i , count in enumerate(piles):
  position = binary_search(count, limits)
  if position == -1:
    limits.append((i, count))
    counter[i] += 1
  else:
    limit_index, limit = limits[position]
    counter[limit_index] += 1
    gaps[limit_index] -= limit - count
    
results = defaultdict(int)
#print limits
total = 0
for position in xrange(len(limits)-1,0,-1):
  limit_index, limit = limits[position]
  #print (total + counter[limit_index]) ,  (limit - limits[position -1][1]) ,gaps[limit_index]
  results[limit_index] = (total + counter[limit_index]) * (limit - limits[position -1][1]) + gaps[limit_index]
  total += counter[limit_index]

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def readln():
    _res = list(map(int,str(input()).split(' ')))
    return _res

n = int(input())
a = readln()
c = sorted([[-a[i],i]for i in range(0,n)])
ans = [0 for i in range(0,n)]
front = c[0][1]
for i in range(1,n):
    ans[front] = ans[front] + i * (c[i][0] - c[i-1][0])
    if front > c[i][1]:
        front = c[i][1]

ans[front] = ans[front] + n * (-c[n-1][0])
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from bisect import bisect
n = input()
A = map(int, raw_input().split())
st = [(0, 0)]

part = [0]*(n+1)
block = [0]*(n+1)

for i in xrange(n):
    if st[-1][0] < A[i]:
        st.append((A[i], i))
    idx = bisect(st, (A[i], -1))
    part[idx] += A[i] - st[idx-1][0]
    block[idx-1] += 1
ans = [0]*n
tmp = 0
for i in range(1, len(st))[::-1]:
    tmp += block[i]
    ans[st[i][1]] = tmp*(st[i][0] - st[i-1][0]) + part[i]
print "\n".join(map(str, ans))

Submission status: Accepted

Solution code:
def nibutan(th, a):
    top = len(th)
    btm = 0

    while top > btm:
        mid = (top + btm)//2
        if th[mid] < a <= th[mid + 1]:
            return mid
        elif a <= th[mid]:
            top = mid
        else:
            btm = mid

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

th = [0]
num_th = []
rem = []
max_i = 0
nonzeros = dict()

for i, a in enumerate(A):
    if a > th[-1]:
        th.append(a)
        num_th.append(1)
        rem.append(0)
        nonzeros[i] = max_i
        max_i += 1
    else:
        j = nibutan(th, a)
        if j - 1 >= 0:
            num_th[j - 1] += 1
        rem[j] += a - th[j]

for i in range(len(num_th) - 1, 0, -1):
    num_th[i - 1] += num_th[i]

for i in range(N):
    if i in nonzeros:
        ans = (th[nonzeros[i] + 1] - th[nonzeros[i]])*num_th[nonzeros[i]]
        ans += rem[nonzeros[i]]
        print(ans)
    else:
        print(0)

Submission status: Accepted

Solution code:

def BS(th, a):
    top = len(th)
    btm = 0

    while top > btm:
        mid = (top + btm)//2
        if th[mid] < a <= th[mid + 1]:
            return mid
        elif a <= th[mid]:
            top = mid
        else:
            btm = mid

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

th = [0]
num_th = []
rem = []
max_i = 0
nonzeros = dict()

for i, a in enumerate(A):
    if a > th[-1]:
        th.append(a)
        num_th.append(1)
        rem.append(0)
        nonzeros[i] = max_i
        max_i += 1
    else:
        j = BS(th, a)
        if j - 1 >= 0:
            num_th[j - 1] += 1
        rem[j] += a - th[j]

for i in range(len(num_th) - 1, 0, -1):
    num_th[i - 1] += num_th[i]
'''
print(th)
print(num_th)
print(rem)
'''
for i in range(N):
    if i in nonzeros:
        ans = (th[nonzeros[i] + 1] - th[nonzeros[i]])*num_th[nonzeros[i]] + rem[nonzeros[i]]
        print(ans)
    else:
        print(0)

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    work_array = [[a, b] for a, b in zip([int(i) for i in input().split()], [j for j in range(0, n)])]
    ans_list = [0] * n
    work_array.sort(reverse=True)

    last_num = work_array[0][0]
    min_index = work_array[0][1]
    for counter in range(n):
        current_num = work_array[counter][0]
        if last_num != current_num:
            ans_list[min_index] += counter * (last_num - current_num)
            last_num = current_num
        min_index = min(min_index, work_array[counter][1])

    ans_list[min_index] += (counter + 1) * last_num
    print("\n".join([str(c) for c in ans_list]))

if __name__=="__main__":
    solve()

Submission status: Accepted

Solution code:
n=int(raw_input())
a=[]
for i,j in enumerate(map(int,raw_input().split())):
    a.append([j,i])
a.sort(reverse=True)
now=0
nx=0
ans=[0]*n
cnt=0
idx=10**6
while now<n:
    while nx<n and a[now][0]==a[nx][0]:
        idx=min(idx,a[nx][1])
        cnt+=1
        nx+=1
    if nx==n:
        ans[idx]+=cnt*a[now][0]
    else:
        ans[idx]+=(a[now][0]-a[nx][0])*cnt
    now=nx
for i in xrange(n):
    print ans[i]

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)


values = reversed(sorted(set(a)))
s = 0
m = 0
above = dict()
n_above = dict()
for v in values:
    above[v] = s
    n_above[v] = m
    s += c[v] * v
    m += c[v]
above[0] = s
n_above[0] = m


m = 0
u = [0]
for v in a:
    if v > m:
        u.append(v)
        m = v

r = defaultdict(int)
last = 0
for j, v in enumerate(u):
    r[v] = last - (above[v] - n_above[v] * v)
    last = above[v] - n_above[v] * v



m = 0
for v in a:
    if v > m:
        print(r[v])
        m = v
    else:
        print(0)

Submission status: Accepted

Solution code:
n = int(raw_input())
a = map(int, raw_input().split())
ai = zip(a,range(n))
# ai.sort()

# ans = [0] * n
# prev = 0
# for i in range(n):
#     a,a_i = ai[i]
#     ans[a_i] = (a-prev) * (n-i)
#     prev = a

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

ai.sort()
ai = ai[::-1]
ai.append((0,0)) # dummy

ans = [0] * n
min_a_i = float('inf')
for i in range(n):
    min_a_i = min(min_a_i, ai[i][1])
    ans[min_a_i] += (ai[i][0] - ai[i+1][0]) * (i+1)

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

Submission status: Accepted

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

b.sort(key= lambda x: (-x[0], x[1]))

# print(b)

mini = 0

for i in range(N-1):
    if b[i][1] < b[mini][1]:
        mini = i

    b[mini] = b[mini][0], b[mini][1], b[mini][2] + (b[i][0]-b[i+1][0])*(i+1)

if b[N-1][1] < b[mini][1]:
    mini = N-1
b[mini] = b[mini][0], b[mini][1], b[mini][2] + (b[N-1][0])*N

b.sort(key = lambda x: x[1])

for x in b:
    print(x[2])

Submission status: Accepted

Solution code:
n = int(raw_input())
a = [int(x) for x in raw_input().split()]

mi = []
l = 0
m = 0

for i in xrange(n):
    if a[i] > m:
        mi.append([i, a[i] - m, a[i], 1, m])
        l += 1
        m = a[i]
    else:
        jl = 0
        ju = l
        while jl < ju:
            mid = (jl + ju) / 2
            if mi[mid][2] < a[i]:
                jl = mid + 1
            else:
                ju = mid
        j = jl
        mi[j][3] += 1
        mi[j][1] += a[i] - mi[j][4]

s = 0
for i in xrange(l - 1, 0, -1):
    s += mi[i][3]
    mi[i - 1][1] += (mi[i - 1][2] - mi[i - 1][4]) * s

j = 0
for i in xrange(n):
    if j >= l:
        print 0
        continue
    ii, d, ai, ni, mim = mi[j]
    if ii == i:
        print d
        j += 1
    else:
        print 0

Submission status: Accepted

Solution code:
from sys import stdin
n = int(stdin.readline())
ans = [0] * (n+2)
a = [0] + map(int,stdin.readline().split())
b = []
for i in xrange(1,n+1):
    b.append((a[i],i))
b.sort()
b.reverse()
first = {}
co = {}
for x,y in b:
    if x not in first:
        first[x] = y
    else:
        first[x] = min(first[x],y)
first[0] = 0        
m = set(a)
for i in a:
    co[i] = co.get(i,0) + 1
m = list(m)
m.sort()
m.reverse()
l = len(m)
for i in xrange(l-1):
    cur = m[i]
    fir = co[cur]
    mi = first[cur]
    sec = m[i+1]
    ans[mi]+=(m[i]-m[i+1])*fir
    co[sec] += fir
    first[sec] = min(first[sec],first[cur])
for i in xrange(1,n+1):
    print ans[i]

Submission status: Accepted

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

t = A[0]
indices = [0]
seq = [t]
for i in range(1,N):
  if A[i] > t:
    t = A[i]
    indices.append(i)
    seq.append(t)

M = len(seq)
delta = [seq[0]]+[seq[i+1]-seq[i] for i in range(M-1)]

temp = [0]*M
count = [0]*M


from bisect import bisect_left
for a in A:
  p = bisect_left(seq, a)
  count[p] += a - seq[p]
  temp[p] += 1

t = 0
for i in reversed(range(M)):
  t += temp[i]
  temp[i] = t

for i in range(M):
  count[i] += temp[i]*delta[i]

result = [0]*N
for i,c in zip(indices,count):
  result[i] = c

for r in result:
  print(r)

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()
ans = [0 for i in range(n)]
ans[0] = b[0][0] * n
min_index = b[-1][1]
for i in range(n-1, 0, -1):
    min_index = min(min_index, b[i][1])
    if b[i-1][0] != b[i][0]:
        ans[min_index] += (b[i][0] - b[i-1][0]) * (n-i)
for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()


def main():
    n = II()
    a = LI()
    b = [(a[i], i) for i in range(n)]
    b.sort()
    b.reverse()
    r = [0] * n
    s = sum(a)
    t = inf
    for i in range(n):
        ai,bi = b[i][0],b[i][1]
        if bi == 0:
            r[0] += s
            break
        ti = (ai - b[i+1][0]) * (i+1)
        if t > bi:
            t = bi
        r[t] += ti
        s -= ti
    return '\n'.join(map(str, r))

print(main())

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

N = read()
a = reads()

b = [(-a[i], i) for i in range(N)]
b.sort()
b.append((0, -1))
# print(b)

result = [0] * N

m = b[0][1]
j = 0
for i in range(1, N+1):
  if b[j][0] != b[i][0]:
    # print(j, i, (b[i][0] - b[j][0]))
    result[m] += (b[i][0] - b[j][0]) * i
    j = i
  m = min(m, b[i][1])

# print(" ".join(str(k) for k in result))
for i in range(N):
  print(result[i])

Submission status: Runtime Error

Solution code:
from collections import Counter

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

ans = [0]*n
d = Counter(a)
k = list(d.keys())[::-1]
for i in range(len(k)-1):
    ind = a.index(k[i])
    ans[ind] += d[k[i]]*(k[i]-k[i+1])
    d[k[i+1]] += d[k[i]]
ans[k[-1]-1] += n
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
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)
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: Runtime Error

Solution code:
n = int(input())
a = [int(v) for v in input().split()]
mx = max(a)
b = [0]*mx
for i in range(n): b[a[i]-1]+=1
c = [-1]*mx
for i in range(n):
  if c[a[i]-1]==-1: c[a[i]-1]=i
for i in range(mx-2, -1, -1):
  b[i] += b[i+1]
  if c[i]==-1: c[i] = c[i+1]
res = [0]*n
for i in range(mx): res[c[i]] += b[i]
for i in range(n): print(res[i])

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(v) for v in input().split()]
mx = max(a)
b = [0]*mx
for i in range(n): b[a[i]-1]+=1
c = [-1]*mx
for i in range(n):
  if c[a[i]-1]==-1: c[a[i]-1]=i
for i in range(mx-2, -1, -1):
  b[i] += b[i-1]
  if c[i]==-1: c[i] = c[i+1]
res = [0]*n
for i in range(mx): res[c[i]] += b[i]
for i in range(n): print(res[i])

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.read
from itertools import accumulate

n, *A = map(int, read().split())
S = []
now = 0
for a in A:
  if now < a:
    now = a
    S.append(a)
l = len(S)
C = [0]*l
D = {e:i for i, e in enumerate(S)}
K = [-1]*l
for i, a in enumerate(A):
  idx = D[a]
  if K[idx] == -1:
    K[idx] = i
  C[idx] += 1
S = [0] + S
C = list(accumulate(C[::-1]))[::-1]
L = [0]*n
for i, k in enumerate(K):
  L[k] = (S[i+1]-S[i]) * C[i]
print(*L, sep="\n")

Submission status: Runtime Error

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

cnt =0
for i in range(n):
    if m >= 2:
        m -= 2
        cnt += 1

for j in range(m // 4):
    if m >=4:
        m -= 4
        cnt += 1

print(cnt)

Submission status: Runtime Error

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)
inf.sort(reverse=True)
cnt = [0]*N
for a,i in inf:
  B.bit_add(i,1)
  cnt[i] = B.bit_sum(N-1)-B.bit_sum(i-1)

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

Submission status: Runtime Error

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)
inf.sort(reverse=True)
cnt = [0]*N
for a,i in inf:
  B.bit_add(i,1)
  cnt[i] = B.bit_sum(N-1)-B.bit_sum(i-1)

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