/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 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