Submission #549352

#	Time	Username	Problem	Language	Result	Execution time	Memory
549352		beaconmc	Snowball (JOI21_ho_t2)	Pypy 3	100 / 100	1326 ms	73052 KiB

Main

from bisect import *
n,q = map(int, input().split())
lis = list(map(int, input().split()))

diffs = []
for i in range(n-1):
    diffs.append(abs(lis[i] - lis[i+1]))
ans = [0 for i in range(n)]
queries = []
for i in range(q):
    queries.append(int(input()))


states = [[0,0,0]]

cur = [0,0,0]
pos = 0
for i in range(q):
    pos += queries[i]
    sus = False
    if pos<0 and cur[1]<abs(pos):
        sus = True
        cur[1] = abs(pos)
    elif pos>0 and cur[2] < pos:
        sus = True
        cur[2] = pos

    if sus:
        cur[0] = cur[1] + cur[2]
        states.append(list(cur))

states.sort()

for i in range(n-1):
    sus = bisect(states, [diffs[i]])

    if sus==len(states):
        ans[i+1] += states[-1][1]
        ans[i] += states[-1][2]
    else:
        if states[sus-1][1] == states[sus][1]:
            ans[i+1] += states[sus][1]
            ans[i] += diffs[i] - states[sus][1]
        else:
            ans[i] += states[sus][2]
            ans[i+1] += diffs[i] - states[sus][2]

ans[0] += states[-1][1]
ans[-1] += states[-1][2]

for i in ans:
    print(i)
        

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