Submission #68130460

---

Source Code Expand

from heapq import heapify, heappop, heappush


N=int(input())
PAB=[]
for _ in range(N):
    p,a,b=map(int,input().split())
    PAB.append((p,a,b))

Q=int(input())
X=[(int(input()),i) for i in range(Q)]

heapify(X)
SIZE=1000
pos=[[] for _ in range(SIZE+1)]

total=0
while X:
    x,i=heappop(X)
    if x+total<=SIZE:
        pos[x+total].append(i)
    else:
        heappush(X,(x,i))
        break

for p,a,b in PAB:
    posn=[[] for _ in range(SIZE+1)]
    for t in range(p+1):
        tn=a+t
        if len(pos[t])>len(posn[tn]):
            pos[t],posn[tn]=posn[tn],pos[t]
        posn[tn].extend(pos[t])

    for t in range(p+1,SIZE+1):
        tn=max(0,t-b)
        if len(pos[t])>len(posn[tn]):
            pos[t],posn[tn]=posn[tn],pos[t]
        posn[tn].extend(pos[t])
    
    total-=b
    while X:
        x,i=heappop(X)
        if x+total<=SIZE:
            posn[x+total].append(i)
        else:
            heappush(X,(x,i))
            break
    pos=posn

ans=[-1]*Q
for t,line in enumerate(pos):
    for i in line:
        ans[i]=t
for x,i in X:
    ans[i]=max(0,x+total)
print(*ans,sep="\n")

Submission Info

Judge Result