Intersecting Intervals

题目描述

你有 $N$ 个实数区间。第 $i$ 个 $(1 \leq i \leq N)$ 区间是 $[l_i, r_i]$。求满足 $1 \leq i < j \leq N$ 且第 $i$ 个和第 $j$ 个区间相交的对 $(i, j)$ 的个数。

输入格式

输入从标准输入给出，格式如下： $N$ $l_1$ $r_1$ $l_2$ $r_2$ $\vdots$ $l_N$ $r_N$

输出格式

输出答案。

3
1 5
7 8
3 7

2

3
3 4
2 5
1 6

3

2
1 2
3 4

0

提示

$2 \leq N \leq 5 \times 10^5$ 0 \leq l_i &lt; r_i \leq 10^9 所有输入值均为整数。给定的区间是 $[1,5], [7,8], [3,7]$。在这些区间中，第 $1$ 个和第 $3$ 个区间相交，且第 $2$ 个和第 $3$ 个区间相交，所以答案是 $2$.

标签: AtCoder|abc355D

来源

AtCoder|abc355D