分数: 400 点
问题陈述
给定两个长度为正整数的序列 N, L=(L_1,L_2,\ldots,L_N) 和 R=(R_1,R_2,\ldots,R_N),和一个整数 M.
查找整数对的数量 (l,r) 满足以下两个条件:
- 1\le l \le r \le M
- 对于每个 1\le i\le N,间隔 [l,r] 不完全包含区间 [L_i,R_i].
约束
- 1\le N,M\le 2\times 10^5
- 1\le L_i\le R_i\le M
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M L_1 R_1 L_2 R_2 \vdots L_N R_N
输出
打印答案。
示例输入 1
2 4 1 2 3 4
示例输出 1
5
五对 (l,r)=(1,1),(2,2),(2,3),(3,3),(4,4) 满足条件。
例如, (l,r)=(1,3) 不满足条件,因为间隔 [1,3] 完全包含区间 [1,2].
示例输入 2
6 5 1 1 2 2 3 3 4 4 5 5 1 5
示例输出 2
0
可能存在没有整数对满足条件的情况。
示例输入 3
6 20 8 12 14 20 11 13 5 19 4 11 1 6
示例输出 3
102