分数: 366 分
问题陈述
高桥是气象台的一名工作人员。沿着一条由东向西直线延伸的道路,有 N 观察点,编号 1, 2, \ldots, N 依次,他正在勘察各个点的积雪状况。
最初, 降雪量 在每个点都是 0.
今年冬天,共有 M 降雪。在 i第一场降雪 (1 \leq i \leq M),降雪量增加了 1 从点开始的每一点 L_i 来点 R_i (含)。
换句话说,毕竟 M 降雪已结束,每个点的降雪次数等于该点包含在降雪范围内的总次数。
他的主管青木告诉他“降雪量为 K 或更多需要除雪。”为了制定除雪计划,高桥想要确定降雪量为的点的数量 毕竟 K 或更多 M 降雪已经结束。
查找降雪量为的点数 K 或更多。
约束
- 1 \leq N \leq 10^6
- 1 \leq M \leq 2 \times 10^5
- 1 \leq K \leq M
- 1 \leq L_i \leq R_i \leq N
- 所有输入值均为整数。
输入
N M K L_1 R_1 L_2 R_2 \vdots L_M R_M
- 第一行包含观察点的数量 N, 降雪次数 M,以及阈值 K 要求除雪,用空格分隔。
- 的 i第行 (1 \leq i \leq M) 以下内容 M 行包含左端点 L_i 和右端点 R_i 的范围 i第一场降雪,以空格分隔。
输出
在一行中输出降雪量为的点数 K 或更多。
示例输入 1
10 3 2 1 5 3 7 6 10
示例输出 1
5
示例输入 2
5 3 3 1 2 3 4 4 5
示例输出 2
0
示例输入 3
100 5 3 10 50 20 60 30 70 40 80 50 90
示例输出 3
41
示例输入 4
1000000 4 2 1 500000 250001 750000 500001 1000000 1 1000000
示例输出 4
1000000
示例输入 5
1 1 1 1 1
示例输出 5
1