TopCoder

Achi_kyw
寫程式好幾年結果三年都進不了校隊還去分科的廢物

User's AC Ratio

87.7% (107/122)

Submission's AC Ratio

31.3% (290/926)

Tags

Description

N顆隕石即將墜落在CK市了!!!!!

CK市是一條直線。因為CK市相當地廣大,在這題我們暫時假設CK市沒有盡頭。

CK市的科學家合力估算了N顆隕石墜落的地點。根據計算,第i顆隕石墜落後將破壞[Li,Ri)區間的CK市。也就是說所有座標大於等於Li並小於Ri的地方都會被破壞殆盡。為了防止世界被破壞,CK市的市長祭出了兩個手段。

第一個手段是築起防護罩。每層防護罩都可以籠罩整個CK市。然而如果座標x處受到隕石衝擊,那麼該處的防護罩就會減少一層。不過CK市的防護罩材料特別:一處的結構受損並不會影響到其它地方的結構穩定度。當然,可以築起多層防護罩提供更多的防護。

第二個手段是消滅隕石。然而尤於填充能量費時,在大災難來臨之前,CK市只來得及射下K顆隕石。

雖然當然也可以直接建造N層防護罩,但是建造愈多防護罩意味著愈多的損失。請問在最佳策略下,CK市能建造最少幾層的防護罩讓所有CK市內的地區安然無恙?

Input Format

第一行有一個正整數N105以及一個非負整數KN,分別代表隕石數以及能消滅的隕石個數。
接下來的N行中,每行有兩個整數109Li<Ri109,代表第i顆隕石將會破壞[Li,Ri)區間的城市。

子任務(測資) 額外限制 分數
1 (0~4) K=0,N104,0Li<Ri104 20
2 (0~9) K=0 20
3 (10~14) N17 20
4 (15~19) K=1 20
5 (20~24) K=2 20
6 (25~29) N103 50
7 (25~31) N104 50
8 (0~33) 100

Output Format

請輸出一個非負整數,代表可行方案最少能使用幾層防護罩。

Sample Input 1

3 1
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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 1500 65536 262144 8
33 1500 65536 262144 8