e841. P8. 幽靈寶藏(Treasure)
Tags : greedy 延遲標記? 掃描線
Accepted rate : 75人/135人 ( 56% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-05-09 16:50

Content

y19m08a_p8_幽靈寶藏(Treasure)    2019年,08月,TOI, 新手同好會 {題目連結}

 問題敘述

探險隊在一座廢墟中找到了傳說中的藏寶箱,當他們正要取走寶藏時,出現了傳說中的海盜幽靈,幽靈決定和探險隊的成員玩一個遊戲。

遊戲的規則如下,幽靈會先變出N個空的藏寶箱,並進行以下兩種操作共M次:

(1) 在連續的數個藏寶箱內放入S枚硬幣。

(2) 使連續的數個藏寶箱內的硬幣價值變為S倍,包括事後放入的硬幣。

 當幽靈完成所有操作後,探險隊可以挑選一個寶箱帶走。請你幫探險隊找出價值最高的寶箱。

 

範例說明1:最後寶箱內價值為:2、5、10、10、12。

範例說明2:最後寶箱內價值為:1、6、6、6、6、1,輸出編號最小者。

評分說明本題共有三組測試題組,條件限制如下所示。每組的所有測試資料皆需答對才會獲得該組分數。

子任務1 分數10   額外輸入限制:1<=N, M <=10^2

子任務2 分數30   額外輸入限制:1<=N, M <=10^4

子任務3 分數60   額外輸入限制:1<=N, M <=10^6

 

 

Input

每筆測試資料為M+1列,第一列有兩個正整數N和M(1<=N, M <=10^6),代表有N個空寶箱,編號為1至N,以及M個操作。緊接著M列,每列都有四個正整數P、Q、R、S(1<=P, Q<=N),R只有兩種值1或2,當R為1時,代表幽靈在第P至Q個藏寶箱內放入了S枚硬幣,當R為2時,代表幽靈使第P至Q個藏寶箱的硬幣價值變為S倍,一個寶箱的最終價值不會超過20億。

 

Output

對每筆資料請輸出一列共兩個數字,為最高價值寶箱的編號以及其價值。若有數個寶箱價值相等,請輸出編號最小者。

 

 

Sample Input #1
5 4
3 5 2 2
1 4 1 2
5 5 2 2
2 5 1 3
Sample Output #1
5 12
Sample Input #2
6 5
1 6 1 1
2 3 1 2
3 5 2 2
2 2 1 3
4 5 1 2
Sample Output #2
2 6
Sample Input #3
10 5
2 9 1 99
1 7 2 1249
5 10 2 1
5 6 1 999999
6 7 1 500000
Sample Output #3
6 1873622402
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#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 , <1M
公開 測資點#12 (5%): 1.0s , <10M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#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 :

測資有問題,經liouzhou_101大大提醒,2020/08/27更正重評

感謝 as95624268 提醒,2021/05/05測資更正

經 rollfc 的指導,這題解法應該是

把區間增值拆解為掃描線(sweepline) 搭配 入點和出點的變化量
Tags:
greedy 延遲標記? 掃描線
出處:
2019年08月TOI新手同好會 [管理者: p3a_owhj (阿普二信) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
36506 wubaie (小億) e841
203 2023-07-20 14:21
28261 ptyc4076@gma ... (顏榕嶙(Bernie)) e841
個人見解
607 2021-11-22 22:25