Submission #66126970

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#バグるのうざすぎ
#1-basedでやる
N=int(input())
A=list(map(int,input().split()))
pre=[0]*(N+1)
nxt=[N+1]*(N+1)
st=[]
for i in range(1, N+1):
    while st and A[st[-1]-1]<=A[i-1]:
        st.pop()
    pre[i]=st[-1] if st else 0
    st.append(i)
st=[]
for i in range(N, 0, -1):
    while st and A[st[-1]-1]<A[i-1]:
        st.pop()
    nxt[i]=st[-1] if st else N+1
    st.append(i)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#バグるのうざすぎ
#1-basedでやる

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

pre=[0]*(N+1)
nxt=[N+1]*(N+1)
st=[]
for i in range(1, N+1):
    while st and A[st[-1]-1]<=A[i-1]:
        st.pop()
    pre[i]=st[-1] if st else 0
    st.append(i)

st=[]
for i in range(N, 0, -1):
    while st and A[st[-1]-1]<A[i-1]:
        st.pop()
    nxt[i]=st[-1] if st else N+1
    st.append(i)
    
#P,Qを累積和でとって一気にやりたい
P=[0]*(N+2)#kにつく係数
Q=[0]*(N+2)#定数

#k(a*pi[k])+a*qi[k]
for i in range(1,N+1):
    L=i-pre[i]
    R=nxt[i]-i

    d1,d2=min(L,R),max(L,R)
    T=L+R-1
    a=A[i-1]

    #1<=k<=d1
    P[1]+=a
    P[d1+1]-=a

    #d1<k<=d2
    Q[d1+1]+=a*d1
    Q[d2+1]-=a*d1

    #d2<k<=T
    P[d2+1]+=-a
    P[T+1]-=-a
    Q[d2+1]+=a*(L+R)
    Q[T+1]-=a*(L+R)

for k in range(1,N+1):
    P[k]+=P[k-1]
    Q[k]+=Q[k-1]

#1-based->0-based
ans=[0]*N
for k in range(1,N+1):
    ans[k-1]=P[k]*k+Q[k]
print(*ans)

Submission Info

Judge Result