U729307 ?!区区!?
题目背景
帝都的禁飞区又扩大了,帝都邮电大学的小崔同学对此感到非常绝望,他想知道到底哪还能飞。为了简化计算,小崔只计算某个方向上的禁飞区。
小崔拿到最新通告后发现,禁飞区数量太多了,手工计算已经来不及了。他需要你帮忙计算:在这条从 0 到 L 的空域上,无人机最终还能飞行的总长度是多少。
题目描述
给定一条长度为 L 的空域,范围为 [0, L]。
空管部门划定了 n 个禁飞区,每个禁飞区在空域上的影响范围是一个闭区间 [l_i, r_i]。无人机不能进入任何禁飞区覆盖的空域段。
如果多个禁飞区之间有重叠,重叠部分只算一次禁飞。也就是说,你需要先合并所有禁飞区,再计算被禁飞覆盖的总长度。
请你求出:空域上没有被任何禁飞区覆盖的总长度,即无人机可以飞行的总长度。
输入格式
第一行两个整数 n 和 L,分别表示禁飞区数量和航道总长度。
接下来 n 行,每行两个整数 l_i、r_i,表示一个禁飞区在航道上的影响区间 [l_i, r_i]。
输出格式
输出一个整数,表示无人机可以飞行的航道总长度。
输入输出样例 #1
输入 #1
4 20
2 5
8 12
4 9
15 18
输出 #1
7
说明/提示
数据范围 1 <= n <= 100000
0 <= L <= 10
0 <= l_i <= r_i <= L
所有输入均为整数
答案可能较大,建议使用 long long