/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 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) の 5 つが条件を満たします。
例えば (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
Score : 400 points
Problem Statement
You are given two sequences of positive integers of length N, L=(L_1,L_2,\ldots,L_N) and R=(R_1,R_2,\ldots,R_N), and an integer M.
Find the number of pairs of integers (l,r) that satisfy both of the following conditions:
- 1\le l \le r \le M
- For every 1\le i\le N, the interval [l,r] does not completely contain the interval [L_i,R_i].
Constraints
- 1\le N,M\le 2\times 10^5
- 1\le L_i\le R_i\le M
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M L_1 R_1 L_2 R_2 \vdots L_N R_N
Output
Print the answer.
Sample Input 1
2 4 1 2 3 4
Sample Output 1
5
The five pairs (l,r)=(1,1),(2,2),(2,3),(3,3),(4,4) satisfy the conditions.
For example, (l,r)=(1,3) does not satisfy the conditions because the interval [1,3] completely contains the interval [1,2].
Sample Input 2
6 5 1 1 2 2 3 3 4 4 5 5 1 5
Sample Output 2
0
There may be cases where no pairs of integers satisfy the conditions.
Sample Input 3
6 20 8 12 14 20 11 13 5 19 4 11 1 6
Sample Output 3
102