c045. 202001_3 砍樹

Content

有一個長度為 $L$ 的長條型的林場，$N$ 棵樹種在一排，現階段砍樹必須符合以下的條件：「讓它向左或向右倒下，倒下時不會超過林場的左右範圍之外，也不會壓到其它尚未砍除的樹木。」你的工作就是計算能砍除的樹木。

若 $c_i$ 代表第 $i$ 棵樹的位置座標，$h_i$ 代表高度。向左倒下壓到的範圍為 $[c_i-h_i,c_i]$，而向右倒下壓到的範圍為 $[c_i,c_i+h_i]$。如果倒下的範圍內有其它尚未砍除的樹就稱為壓到，剛好在端點不算壓到。

我們可以不斷找到滿足砍除條件的樹木，將它砍倒後移除，然後再去找下一棵可以砍除的樹木，直到沒有樹木可以砍為止。無論砍樹的順序為何，最後能砍除的樹木是相同的。

Input

第一行為正整數 $N$ 以及一個正整數 $L$，代表樹的數量與林場右邊界的座標。$N \leq 10^5$，$ L \leq 10^9$ 。

第二行有 $N$ 個正整數依序代表這 $N$ 棵樹的座標，座標是從小到大排序的，所有座標不超過 $L$。

第三行有 $N$ 個正整數依序代表樹的高度，所有樹高都不超過 $10^9$。

第 1 子題組共 20 分： $N \leq 10$
第 2 子題組共 40 分： $N \leq 1000$
第 3 子題組共 40 分：無額外限制。

Output

輸出共有兩行，第一行輸出能被砍除之樹木數量，第二行輸出能被砍除之樹木中最高的高度，如果無法砍除任何一棵樹，則最高高度輸出 0。

Sample Input #1

6 140
10 30 50 70 100 125
30 15 55 10 55 25

Sample Output #1

4
30

Sample Input #2

1 10
5
6

Sample Output #2

0
0

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 0.5s , <1K
公開測資點#2 (5%): 0.5s , <1K
公開測資點#3 (5%): 0.5s , <1K
公開測資點#4 (5%): 0.5s , <1M
公開測資點#5 (5%): 0.5s , <1M
公開測資點#6 (5%): 0.5s , <1M
公開測資點#7 (5%): 0.5s , <1M
公開測資點#8 (5%): 0.5s , <1M
公開測資點#9 (5%): 0.5s , <1M
公開測資點#10 (5%): 0.5s , <1M
公開測資點#11 (5%): 0.5s , <1M
公開測資點#12 (5%): 0.5s , <10M
公開測資點#13 (5%): 0.5s , <10M
公開測資點#14 (5%): 0.5s , <10M
公開測資點#15 (5%): 0.5s , <10M
公開測資點#16 (5%): 0.5s , <10M
公開測資點#17 (5%): 0.5s , <10M
公開測資點#18 (5%): 0.5s , <10M
公開測資點#19 (5%): 0.5s , <10M

Hint ：

Tags:

出處:

2020年1月 APCS 演算法海牛 [管理者：

ktlai (K．我已霸榜．Tlai)

]

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