D - Intersecting Intervals Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 400

問題文

N 個の実数の区間が与えられます。i\,(1 \leq i \leq N) 番目の区間は [l_i,r_i] です。i 番目の区間と j 番目の区間が共通部分を持つような組 (i,j)\,(1\leq i < j \leq N) の個数を求めてください。

制約

  • 2 \leq N \leq 5 \times 10^5
  • 0 \leq l_i < r_i \leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
l_1 r_1
l_2 r_2
\vdots
l_N r_N

出力

答えを出力せよ。


入力例 1

3
1 5
7 8
3 7

出力例 1

2

与えられた区間は [1,5], [7,8], [3,7] です。このうち,1 番目と 3 番目、 2 番目と 3 番目の区間が共通部分を持つため、答えは 2 です。


入力例 2

3
3 4
2 5
1 6

出力例 2

3

入力例 3

2
1 2
3 4

出力例 3

0

Score : 400 points

Problem Statement

You are given N intervals of real numbers. The i-th (1 \leq i \leq N) interval is [l_i, r_i]. Find the number of pairs (i, j)\,(1 \leq i < j \leq N) such that the i-th and j-th intervals intersect.

Constraints

  • 2 \leq N \leq 5 \times 10^5
  • 0 \leq l_i < r_i \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
l_1 r_1
l_2 r_2
\vdots
l_N r_N

Output

Print the answer.


Sample Input 1

3
1 5
7 8
3 7

Sample Output 1

2

The given intervals are [1,5], [7,8], [3,7]. Among these, the 1-st and 3-rd intervals intersect, as well as the 2-nd and 3-rd intervals, so the answer is 2.


Sample Input 2

3
3 4
2 5
1 6

Sample Output 2

3

Sample Input 3

2
1 2
3 4

Sample Output 3

0