f816. TOI_y21m4_a02Youtube
標籤 : pq+前綴和 二分搜+前綴和?
通過比率 : 98人/118人 ( 83% ) [非即時]
評分方式:
Tolerant

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

內容

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

 

輸入說明

第一行輸入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天的討論下降度。

輸出說明

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

範例輸入 #1
3
3 0
3 1
3 2
範例輸出 #1
3
5
4
範例輸入 #2
3
6 2
1 2
4 2
範例輸出 #2
6
5
6
範例輸入 #3
8
10 2
5 3
3 1
20 4
6 3
8 2
5 4
7 2
範例輸出 #3
10
12
13
22
23
27
20
21
測資資訊:
記憶體限制: 256 MB
提示 :

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

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

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
34184 dfd8282@gmai ... (fishhh) f816
解題報告
320 2023-03-04 10:04
31771 forkidlai (forkidlai) f816
python AC tip
412 2022-08-18 15:34