103553: [Atcoder]ABC355 D - Intersecting Intervals

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

问题描述

给你$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