d101: Q-7-11. 紅白彩帶 (APCS201902)
Tags : DSU 圖論
Accepted rate : 142人/191人 ( 74% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-03-26 18:28

Content

一條彩帶被分成 n 個相同大小的格子,有的格子是紅色,有些則是白色。

小軒拿到彩帶後開始塗顏色,每次會將一個白色格子塗滿紅色,然後小軒會算一算目前最長與最短紅色區域的長度佔了幾格,相鄰的紅色格子就屬於同一個紅色區域。小軒一共塗了 k 次,

請你計算出每一次紅色區域的最大與最小長度,並輸出個別的總和。

彩帶可以看成一維陣列,以 0 表示白色,而 1 表示紅色。彩帶的格子從 1 開始由左而右依序編號,小軒每次將某個格子塗上紅色。

 

以下是一個例子。

格子編號               1 2 3 4 5 6 7 8 9

剛開始的彩帶        0 1 1 0 0 1 0 1 0

一開始紅色區域最大的長度是 2,最小的長度是 1。

第1次塗在第5格後 0 1 1 0 1 1 0 1 0

第1次塗完後最長的紅色區域有 2 塊,長度都是 2,最小的長度是 1。

第2次塗在第1格後 1 1 1 0 1 1 0 1 0

第2次塗完後紅色區域的最大長度是3,最小長度是1。

第3次塗在第7格後 1 1 1 0 1 1 1 1 0

第3次塗完後紅色區域的最大長度是4,最小長度是3。

以這個例子而言,每一次(包含剛開始) 紅色區域的最大長度總和是 2+2+3+4=11;

而紅色區域的最小長度總和是 1+1+1+3=6。

Input

輸入有三行,

第一行是兩個整數,依序是 $ n $ 與 $ k $ ,代表彩帶長度以及小軒塗色的次數,$n ≤ 1e5$ 、 $k ≤ 2e4$ 。

第二行有 $ n $ 個 $ 0 $ 或 $ 1 $ 的數字,依序代表彩帶第 $ 1 $ 格至第 $ n $ 格的顏色, $0 $ 代表白色, $1 $ 代表紅色。

第三行有 $ k $ 個數字,依序代表每一次塗紅色的格子編號,若 $ k = 0$ ,則第三行為空行。

同一行數字之間都是以空白間隔。

小軒每次一定都塗在白色格子上,而且最大的紅色區域長度不會超過 $ 1e4 $ 。

Output

輸出兩行,

第一行是每次紅色區域最大長度的總和,

第二行是每次紅色區域最小長度的總和。

Sample Input #1
5 1
1 0 1 0 1
2
Sample Output #1
4
2
Sample Input #2
9 3
0 1 1 0 0 1 0 1 0
5 1 7
Sample Output #2
11
6
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <1M
公開 測資點#3 (20%): 1.0s , <1M
公開 測資點#4 (20%): 1.0s , <1M
Hint :
Tags:
DSU 圖論
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\ \mathtt{Comp.}\ \&\ \mathsf{Info.}\ \mathit{Club}$)
]


ID User Problem Subject Hit Post Date
159
william92110... (Gonjo9)
d101
C++比較簡單解
269 2023-07-21 13:17