f339: 下雪的日子(Snow)
Tags :
Accepted rate : 125人/134人 ( 93% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-10-24 21:43

Content

 2020年8月TOI新手同好會      原題連結

  下雪的日子(Snow)

問題敘述

小豪住的地方常常下雪,每次下雪,住家附近的道路都會被雪掩埋而無法行走,所以小豪必須把雪鏟開才能夠使道路正常運行。小豪可以搜集到關於道路狀況的資訊,並回報給你。舉例來說,若今天小豪回報給你兩組數字[1,3]以及[4,5],代表道路區段[1,3]和[4,5]是暢通的,而區段[0, 1] 和[3, 4] 就不是了。

請撰寫一個程式,給定道路總長度以及搜集到的道路資訊,判斷哪些道路區段目前無法行走。

 

 

評分說明 每筆測資獨立計分。

評分說明 此題目測資分成三組,每組測資有多筆測試資料,需答對該組所有測試資 料才能獲得該組分數。各組詳細限制如下。

第一組 (10 分) : 1<=N<=10、0<=M<=30

第二組 (30 分) : 1<=N <=10^3、0<=M<=10^4

第三組 (60 分) : 1<=N<=10^5、0<=M<=10^6

Input

第一行有兩個整數N與M(1<=N<=20、1<=M<=N),以空格間隔,其中N代表道路總長度,M 代表道路資訊筆數。道路起點皆從0開始。

接下來的M行,每行都有兩個整數S與E(0<=S<=E<=N),為觀察並回傳之道路資訊,S代表的是目前觀察到暢通道路之起點,E代表的是目前觀察到暢通道路之終點。

Output

尋找被雪埋住的路段區段,輸出該區段的左界以及右界。各區段請依其左界由小到大輸出,且任兩區段不重疊。測資保證至少有一單位的路被雪埋住。

Sample Input #1
7 5
0 1
1 3
4 5
5 6
6 7
Sample Output #1
3 4
Sample Input #2
5 2
0 1
3 4
Sample Output #2
1 3
4 5
Sample Input #3
10 4
1 2
3 4
5 6
7 8
Sample Output #3
0 1
2 3
4 5
6 7
8 10
Sample Input #4
6 3
3 5
1 4
5 6
Sample Output #4
0 1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1K
公開 測資點#11 (5%): 1.0s , <1K
公開 測資點#12 (5%): 1.0s , <1K
公開 測資點#13 (5%): 1.0s , <1K
公開 測資點#14 (5%): 1.0s , <1K
公開 測資點#15 (5%): 1.0s , <1K
公開 測資點#16 (5%): 1.0s , <1K
公開 測資點#17 (5%): 1.0s , <1K
公開 測資點#18 (5%): 1.0s , <1K
公開 測資點#19 (5%): 1.0s , <1K
Hint :
Tags:
出處:
TOI2020年8月新手同好會 [管理者:
p3a_owhj (阿普二信)
]


ID User Problem Subject Hit Post Date
23311
a31185367 (Jeffrey)
f339
我的思路想法
373 2020-11-06 19:58
23161
joeliao (RRRrrrr!!!)
f339
提示
316 2020-10-26 22:11