a120:
線段覆蓋長度(測資加強版)
內容
給定一維座標上一些線段，求這線段所覆蓋的長度，注意重疊部分只能算一線段所覆蓋的長度，注意重疊部分只能算一次。例如給定三個線段 ：(5, 6) 、(1, 2) 、(4, 8) 、和 (7, 9) ，如下圖，線段覆蓋長度為6。
輸入說明
第一列是 2 個正整數 n,m，表示此測試案例有 n 個線段，以及座標的範圍。
接著的 n 列，每一列是一個線段的開始端點座標和結束端點座標整數值，開始端點座標值(L)小於等結束端點座標值(R)，兩者之間以一個空格區隔。
保證所有的座標值 (L、R) 滿足 0 ≤ L < R ≤ m 。
輸出說明
輸出其總覆蓋的長度
範例輸入
#1
5 350 160 180 150 200 280 300 300 330 190 210
範例輸出
#1
110
範例輸入
#2
4 10 1 2 5 6 4 8 7 9
範例輸出
#2
6
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (5%): 2.0s , <1K
公開 測資點#1 (5%): 2.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1K
公開 測資點#4 (5%): 2.0s , <1K
公開 測資點#5 (5%): 2.0s , <1M
公開 測資點#6 (5%): 2.0s , <1M
公開 測資點#7 (5%): 2.0s , <1M
公開 測資點#8 (5%): 2.0s , <1M
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (5%): 2.0s , <10M
公開 測資點#11 (5%): 2.0s , <10M
公開 測資點#12 (5%): 2.0s , <10M
公開 測資點#13 (5%): 2.0s , <10M
公開 測資點#14 (5%): 2.0s , <10M
公開 測資點#15 (5%): 2.0s , <10M
公開 測資點#16 (5%): 2.0s , <10M
公開 測資點#17 (5%): 2.0s , <10M
公開 測資點#18 (5%): 2.0s , <10M
公開 測資點#19 (5%): 2.0s , <10M
公開 測資點#0 (5%): 2.0s , <1K
公開 測資點#1 (5%): 2.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1K
公開 測資點#4 (5%): 2.0s , <1K
公開 測資點#5 (5%): 2.0s , <1M
公開 測資點#6 (5%): 2.0s , <1M
公開 測資點#7 (5%): 2.0s , <1M
公開 測資點#8 (5%): 2.0s , <1M
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (5%): 2.0s , <10M
公開 測資點#11 (5%): 2.0s , <10M
公開 測資點#12 (5%): 2.0s , <10M
公開 測資點#13 (5%): 2.0s , <10M
公開 測資點#14 (5%): 2.0s , <10M
公開 測資點#15 (5%): 2.0s , <10M
公開 測資點#16 (5%): 2.0s , <10M
公開 測資點#17 (5%): 2.0s , <10M
公開 測資點#18 (5%): 2.0s , <10M
公開 測資點#19 (5%): 2.0s , <10M
提示 ：
greedy, suffix/prefix method, sortings, data structures (CF 1600)
10%的測資滿足，1 ≤ n ≤ 100 ， 0 ≤ m ≤ 1000 ，並且線段沒有重疊。
15%的測資滿足，1 ≤ n ≤ 100 ， 0 ≤ m ≤ 1000 ，並且線段可能重疊。
25%的測資滿足，1 ≤ n ≤ 10000 ， 0 ≤ m ≤ 106 ，並且線段可能重疊。
50%的測資滿足，1 ≤ n ≤ 200000 ， 0 ≤ m ≤ 109 ，並且線段可能重疊。
標籤:
出處:
apcs
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||