1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
g = [0]+[inf]*n
Q = deque([[0,1,n]])
for j in range(1,n+1):
while Q and Q[0][2]<j:
Q.popleft()
g[j] = w(Q[0][0],j)
while Q and w(j,Q[-1][1])<w(Q[-1][0],Q[-1][1]):
Q.pop()
if not Q:
Q.append([j,j+1,n])
else:
a = bisect_left(range(Q[-1][2]+1),True,j,key=lambda a:w(j,a)<w(Q[-1][0],a))
Q[-1][2] = a-1
if a<=n:
Q.append([j,a,n])
return g
|