103553: [Atcoder]ABC355 D - Intersecting Intervals

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:11 Solved:0

Description

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

Output

分数:$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

加入题单

算法标签: