分数: 366 分
问题陈述
高桥正在用油漆粉刷一面长长的水平墙。
墙延伸到整条数轴,最初,数轴上的每个点都已被绘制 0 次。高桥表演 N 喷漆作业。 i第次操作 (1 \leq i \leq N),他画了区间 [L_i, R_i] (其中 L_i < R_i)一次。也就是说,对于每一个对应实数的点 x 满意 L_i \leq x \leq R_i,已绘制的次数增加了 1.
已涂漆的零件 K 或更多次被认为足够厚并通过检查,而涂漆次数少于 K 时间太薄而失败。
所有操作完成后,找到 总长度 已绘制的所有点的集合的 已绘制的所有点的集合 K 或更多次(即构成该集合的每个区间的长度之和)。
例如,如果绘制的所有点的集合 K 或多次是间隔的并集 [1, 5] 和 [7, 9],答案是 (5 - 1) + (9 - 7) = 6.
请注意,由于所有 L_i 和 R_i 是整数,绘制计数变化的边界仅发生在整数坐标处。因此,答案始终是整数。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 0 \leq L_i < R_i \leq 10^9
- 所有输入值均为整数
输入
N K L_1 R_1 L_2 R_2 \vdots L_N R_N
- 第一行包含一个整数 N 表示绘画操作的次数和一个整数 K 代表通过检查所需的涂层阈值数量,以空格分隔。
- 的 i- 以下各项 N 行 (1 \leq i \leq N) 包含左端点 L_i 和右端点 R_i 中绘制的间隔 i第一个操作,以空格分隔。
输出
输出所有绘制点集合的总长度 K 或多次,作为单行上的整数。
示例输入 1
3 2 1 5 3 7 6 9
示例输出 1
3
示例输入 2
2 2 0 3 5 8
示例输出 2
0
示例输入 3
8 3 0 10 2 8 4 12 1 6 5 15 7 9 3 11 10 14
示例输出 3
10
示例输入 4
15 4 0 100 10 90 20 80 30 70 40 60 5 50 15 85 25 75 35 65 45 55 0 30 50 100 60 95 70 88 3 47
示例输出 4
85
示例输入 5
1 1 0 1000000000
示例输出 5
1000000000