a350. TOI 2020/10 潛力組：著色

題目描述

有一條分成 M 格的紙條，格子由左至右編號 1 到 M。小明共著色 N 次，每次將一段連續區間的所有格子畫滿。每格在累積著色次數達到 K 時便會破損。請計算全部著色完成後，破損的格子數。

輸入格式

第一行為 M、N、K，分別是格子數、著色次數及破損門檻。

• 1 ≤ M ≤ 10^9
• 1 ≤ N ≤ 10^5
• 1 ≤ K ≤ 10^5

接著 N 行，第 i 行為 X_i、Y_i，表示第 i 次將編號 X_i 到 Y_i 的格子著色，兩端皆包含。1 ≤ X_i ≤ Y_i ≤ M。同一行整數以空白分隔。

輸出格式

輸出一行整數，表示至少被著色 K 次的格子數。

原題分組限制

每組各 25 分：第一組 M=10、N≤10；第二組 M=10^6；第三組 M=10^9、K=1；第四組 M=10^9。

範例 1

輸入：

10 3 2
3 3
6 9
7 10

輸出：

3

範例 2

輸入：

10 2 2
1 9
10 10

輸出：

0

來源

TOI 2020 年 10 月練習賽潛力組，依官方 PDF 整理。

官方原題：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202010/Coloring.pdf

標籤：TOI 歷屆