Submission #635013

#	Time	Username	Problem	Language	Result	Execution time	Memory
635013		karolb2011	Snowball (JOI21_ho_t2)	Pypy 3	100 / 100	1193 ms	69040 KiB

Main

import sys
input=sys.stdin.readline
n,q=list(map(int,input().split()))
x=list(map(int,input().split()))
y=[]
for i in range(n-1):
    y.append([x[i+1]-x[i],i])
wc=0
wm=0
ws=0
y.sort(reverse=True)
L=[0 for i in range(n)]
R=[0 for i in range(n)]
for i in range(q):
    z=int(input())
    wc+=z
    wm=max(wc,wm)   
    ws=min(wc,ws)
    L[0]=-ws
    R[n-1]=wm
    while len(y) and wm-ws>=y[-1][0]:
        c,i=y.pop()
        if z<0:
            L[i+1]=min(-ws,c-wm)
            R[i]=wm
        else:
            R[i]=min(wm,c+ws)
            L[i+1]=-ws
for c,i in y:
    L[i+1]=-ws
    R[i]=wm
for i in range(n):
    print(R[i]+L[i])

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67