# ZJ f816. TOI_y21m4_a02Youtube
[ZJ f816](https://zerojudge.tw/ShowProblem?problemid=f816)

## 說明：
nx[]: 動態存放熱門度還未歸0的清單排序大到小清單
利用python內建bisect.insort(nx,value)將value插入nx只能小到大排序，所以把value加上負號存放，取值時再加上負號反正

total_reduce：累積的討論下降度
total_live：累積熱門度
v,d = 第i天的討論度，下降度

第i天，從小到大逐一檢查還在的nx，若nx[-1]<total_reduce+第i天討論下降度d，則表示第i天該項會低於0，所以pop()，檢查到不需pop()時跳開
每次pop()前，要把total_live扣掉(nx[-1]-total_reduce)
因原先nx[-1]在塞入時有加上當時的total_reduce(持續累積到目前的)

把第i天的(當天討論度v+累積至當天的討論下降度total_reduce)塞入nx：bisect.insort(nx,-(v+total_reduce))
### 參考 https://www.youtube.com/watch?v=H5szn7--Dpg
## code
AC (1.9s, 34.2MB)

# 2021	4	f816: TOI_y21m4_a02Youtube
# 參考 https://www.youtube.com/watch?v=H5szn7--Dpg
# 因為要讀入的資料量大，所以改用sys.stdin.readlines()一次讀入減少IO，才能AC，若用input()，只能90%
# bisect.insort只能插入小到大的陣列，因此用負值才能實現大到小排序，取值時記得加上負號

import bisect
import sys

# n = int(input())
vd = sys.stdin.readlines()
nx = []
total_reduce = 0
total_live = 0
for i in range(1,int(vd[0])+1):
    v,d = map(int,vd[i].split())
    # v,d = map(int,input().split())
    while len(nx):
        if (-nx[-1]<=total_reduce + d): #nx[-1]取值時外面記得加上負號
            total_live -= -nx[-1] - total_reduce
            nx.pop()
        else:
            break
    total_reduce +=d
    total_live -= d*(len(nx))

    bisect.insort(nx,-(v+total_reduce)) #bisect.insort只能插入小到大的陣列，因此用負值才能實現大到小排序，取值時記得加上負號
    total_live += v    
    # print(nx,total_reduce,total_live)
    print(total_live)

###### tags: `python` `bisect` `二分搜` `TOI` `DP`