f816: TOI_y21m4_a02Youtube
Tags : pq+前綴和 二分搜+前綴和?
Accepted rate : 37人/48人 ( 77% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-05-04 15:53

Content

TOI練習賽2021年4月_潛力組-2Youtube頻道(Youtube),  原始試題檔

第i天會將第1~i-1天的討論度皆降di,然後(加總第1~第i天的討論度)後輸出{即熱門度}
最低降為0,不會降為負的


測資3說明:
第i天    1     2     3     4     5     6     7    8
vi      10     5     3    20     6     8    5    7                                     
di        2     3     1      4     3     2    4    2                
熱門度 10  12    13   22    23   27   20  21

第1天   10
第2天   7 + 5
第3天   6 + 4  + 3 
第4天   2 + 0  + 0  + 20
第5天   0 + 0  + 0  + 17  + 6
第6天   0 + 0  + 0  + 15  + 4 + 8
第7天   0 + 0  + 0  + 11  + 0 + 4 + 5
第8天   0 + 0  + 0  + 9   + 0 + 2 + 3 + 7

 

Input

第一行輸入1個正整數D(1<=D<=4*10^5),表示經營Youtube頻道起D天內每天的熱門程度分別為多少。
接下來的D行,每行有2個非負整數vi(0<=vi<=10^9),di(0<=di<=10^9),其中vi為第i天的討論度,di為第i天的討論下降度。

Output

共D行,每行輸出一個整數,代表第i天的熱門程度

Sample Input #1
3
3 0
3 1
3 2
Sample Output #1
3
5
4
Sample Input #2
3
6 2
1 2
4 2
Sample Output #2
6
5
6
Sample Input #3
8
10 2
5 3
3 1
20 4
6 3
8 2
5 4
7 2
Sample Output #3
10
12
13
22
23
27
20
21
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1M
公開 測資點#3 (5%): 1.0s , <1M
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <10M
公開 測資點#10 (5%): 1.0s , <10M
公開 測資點#11 (5%): 1.0s , <10M
公開 測資點#12 (5%): 1.0s , <10M
公開 測資點#13 (5%): 1.0s , <10M
公開 測資點#14 (5%): 1.0s , <10M
公開 測資點#15 (5%): 1.0s , <10M
公開 測資點#16 (5%): 1.0s , <10M
公開 測資點#17 (5%): 1.0s , <10M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <10M
Hint :

感謝 rollfc (胖胖貓) 的指導
使用的方法是 priority_queue + 前綴和

Tags:
pq+前綴和 二分搜+前綴和?
出處:
toi練習賽2021年4月潛力組 [管理者:
p3a_owhj (阿普二信)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」