2024 全國模擬賽題目上線啦 !!!!! 題目在這裡～
1819 . 綿羊山
TopCoder
Tags
Description
有天你閒來沒事，所以你就去爬綿羊山(因為魯蛋沒開台)...
但是你突然發現爬綿羊山好累...所以你決定算一下爬綿羊山浪費體力的程度是多少=w=
綿羊山其實是一座山脈，山地跟平地的交界處剛好都在數線上的整數座標上，爬綿羊山浪費體力的程度為"連續山地的數量"
這時邪惡的小綿羊看到你在爬山，所以他決定派出N組軍隊，每組被分配到一個任務區間i, j，表示從座標 i 一路改造到座標 j ，軍隊會把i 到 j 之間的平地改造成山地、山地改造成平地。
每組軍隊改造完後都會有一個「爬綿羊山浪費體力的程度」。
現在你想知道所有「爬綿羊山浪費體力的程度」中的最大值。
Input Format
第一行有兩個正整數N, M，表示小綿羊派出的軍隊數及綿羊山的長度。
接下來N行依序為小綿羊派出的軍隊，每行有兩個正整數a, b，表示軍隊從a一路改造到b。
占總分30% N, M <= 1,000
占總分60% N <= 1,000 且 M < 231
占總分60% N, M <= 100,000
所有資料滿足 1 <= a,b <=M
且N < 100,000 ,M < 231
Output Format
輸出一個你認為是答案的東西
Sample Input 1
5 10
2 4
5 9
6 8
3 4
1 5
2 4
5 9
6 8
3 4
1 5
Sample Output 1
3
Hints
範例測資中，「爬綿羊山浪費體力的程度」最大的情況有兩種：
平高平平高平平高平平 -> 三段
高平高高平平平高平平 -> 三段
一開始綿羊山是一塊平地，而且軍隊不一定會往前，也有可能往後走。
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~9 | 100 |