f816. TOI_y21m4_a02Youtube - 高中生程式解題系統

內容

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

範例輸出 #1

3
5
4

範例輸入 #2

範例輸出 #2

6
5
6

範例輸入 #3

範例輸出 #3

測資資訊：

記憶體限制： 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

提示：

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

標籤:

pq+前綴和二分搜+前綴和？

出處:

toi 練習賽 2021年 4月潛力組 [管理者： p3a_owhj (阿普二信) ]

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

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

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

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