Problem : 338 - pB.嘉慶王朝

Problem Statistics

Solved Member: 17　　Submission: 116　　User Tried: 32

Statement:

嘉慶是清朝入關後第五位皇帝「清仁宗愛新覺羅顒琰」的年號
公元1796年37歲(虛歲)即位，前後共二十五年。 By wiki

上文跟本題沒有任何關聯，我們親愛的嘉慶帝現在要整頓他的帝國。
已知嘉慶帝國由M個城市排成一直線組成，依序編號1到M。每個城市會有「平地」跟「高地」兩種狀態，一開始每個城市都是平地，但這樣的地形太危險了，隔壁的宮嚴王朝很可能長驅直入，所以嘉慶希望國內的地形更容易防守。容易防守的程度定義為「國家內有多少組連續高地」。
現在大臣鍾意提出了一個方案 : 依序派出N組軍隊，每組被分配到一個任務區間[i, j]，表示從城市 i 一路改造到城市 j ，軍隊會把路過的平地改造成高地、高地改造成平地。
每組軍隊改造完後都會有一個「容易防守的程度」。現在嘉慶想知道所有「容易防守的程度」的最大值，於是他請你寫一個程式計算，整個過程中嘉慶王朝最容易防守的程度。

Input:Output:

第一行有兩個正整數N, M，表示鍾意派出的軍隊數及嘉慶帝國的長度。
接下來N行依序為鍾意派出的軍隊，每行有兩個正整數a, b，表示軍隊從a一路改造到b。

輸出一個數字表示嘉慶王朝容易防守的程度

Sample Input:Sample Output:

5 10
2 4
5 9
6 8
3 4
1 5

HINT:

占總分30% N, M <= 1,000
占總分60% N <= 1,000 且 M < 2^31
占總分60% N, M <= 100,000
所有資料滿足 1 <= a <= b <=M
且N < 100,100 ,M < 2^31
-
範例測資中，嘉慶帝國的地形最好的情況有兩種：
平高平平高平平高平平 -> 三段
高平高高平平平高平平 -> 三段

Source:

103附中校內賽

Problem Setter

IPJ

Testdata:

Test	Time	Memory	Score
0	1000ms	262144kb
1-1	1000ms	262144kb	30
1-2	1000ms	262144kb
1-3	1000ms	262144kb
1-4	1000ms	262144kb
1-5	1000ms	262144kb
2-1	1000ms	262144kb	30
2-2	1000ms	262144kb
2-3	1000ms	262144kb
3-1	1000ms	262144kb	30
3-2	1000ms	262144kb
3-3	1000ms	262144kb
4-1	1000ms	262144kb	10
4-2	1000ms	262144kb
4-3	1000ms	262144kb