TopCoder

Thumb 1
羽瀨川小鷹
我是布丁

User's AC Ratio

87.5% (42/48)

Submission's AC Ratio

24.3% (122/503)

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

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

Testdata and Limits

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