1337 . 隕石
TopCoder
Tags
Description
有$N$顆隕石即將墜落在CK市了！！！！！
CK市是一條直線。因為CK市相當地廣大，在這題我們暫時假設CK市沒有盡頭。
CK市的科學家合力估算了$N$顆隕石墜落的地點。根據計算，第$i$顆隕石墜落後將破壞$[L_i, R_i)$區間的CK市。也就是說所有座標大於等於$L_i$並小於$R_i$的地方都會被破壞殆盡。為了防止世界被破壞，CK市的市長祭出了兩個手段。
第一個手段是築起防護罩。每層防護罩都可以籠罩整個CK市。然而如果座標$x$處受到隕石衝擊，那麼該處的防護罩就會減少一層。不過CK市的防護罩材料特別：一處的結構受損並不會影響到其它地方的結構穩定度。當然，可以築起多層防護罩提供更多的防護。
第二個手段是消滅隕石。然而尤於填充能量費時，在大災難來臨之前，CK市只來得及射下$K$顆隕石。
雖然當然也可以直接建造$N$層防護罩，但是建造愈多防護罩意味著愈多的損失。請問在最佳策略下，CK市能建造最少幾層的防護罩讓所有CK市內的地區安然無恙？
Input Format
第一行有一個正整數$N\leq 10^ 5$以及一個非負整數$K\leq N$，分別代表隕石數以及能消滅的隕石個數。
接下來的$N$行中，每行有兩個整數$-10^ 9\leq L_i < R_i \leq 10^ 9$，代表第$i$顆隕石將會破壞$[L_i,R_i)$區間的城市。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~4) | $K=0, N\leq 10^ 4, 0\leq L_i < R_i \leq 10^ 4$ | 20 |
| 2 (0~9) | $K=0$ | 20 |
| 3 (10~14) | $N\leq 17$ | 20 |
| 4 (15~19) | $K=1$ | 20 |
| 5 (20~24) | $K=2$ | 20 |
| 6 (25~29) | $N\leq 10^ 3$ | 50 |
| 7 (25~31) | $N\leq 10^ 4$ | 50 |
| 8 (0~33) | 無 | 100 |
Output Format
請輸出一個非負整數，代表可行方案最少能使用幾層防護罩。
Sample Input 1
3 1
1 4
2 5
4 7
1 4
2 5
4 7
Sample Output 1
1
Hints
Problem Source
Problem Set / Description by Paupière
建國中學105學年度校隊補選pD
(2017.9.23 測資修正 by Paupière. 感謝nonamefour0210)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 20 |
| 2 | 0~9 | 20 |
| 3 | 10~14 | 20 |
| 4 | 15~19 | 20 |
| 5 | 20~24 | 20 |
| 6 | 25~29 | 50 |
| 7 | 25~31 | 50 |
| 8 | 0~33 | 100 |