TopCoder

Thumb tumblr nlxw0sxc2d1unbsixo1 540
Trash
><

User's AC Ratio

90.0% (27/30)

Submission's AC Ratio

34.6% (91/263)

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

3 1
1 4
2 5
4 7

Sample Output

1

Hints

Problem Source

Problem Set / Description by Paupière
建國中學105學年度校隊補選pD
(2017.9.23 測資修正 by Paupière. 感謝nonamefour0210)

Subtasks

For Testdata: 0 ~ 4, Score: 20
For Testdata: 0 ~ 9, Score: 20
For Testdata: 10 ~ 14, Score: 20
For Testdata: 15 ~ 19, Score: 20
For Testdata: 20 ~ 24, Score: 20
For Testdata: 25 ~ 29, Score: 50
For Testdata: 25 ~ 31, Score: 50
For Testdata: 0 ~ 33, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 1000 65536 262144
11 1000 65536 262144
12 1000 65536 262144
13 1000 65536 262144
14 1000 65536 262144
15 1000 65536 262144
16 1000 65536 262144
17 1000 65536 262144
18 1000 65536 262144
19 1000 65536 262144
20 1000 65536 262144
21 1000 65536 262144
22 1000 65536 262144
23 1000 65536 262144
24 1000 65536 262144
25 1000 65536 262144
26 1000 65536 262144
27 1000 65536 262144
28 1000 65536 262144
29 1000 65536 262144
30 1000 65536 262144
31 1000 65536 262144
32 1000 65536 262144
33 1000 65536 262144