Count Median

题目描述

有 $N$ 个整数 $X_1, X_2, \cdots, X_N$，且已知 $A_i \leq X_i \leq B_i$。 求 $X_1, X_2, \cdots, X_N$ 的中位数可能取的不同值的个数。

输入格式

输入按照如下格式从标准输入给出： $N$ $A_1$ $B_1$ $A_2$ $B_2$ : $A_N$ $B_N$

输出格式

输出答案。

2
1 2
2 3

3

3
100 100
10 10000
1 1000000000

9991

提示

$2 \leq N \leq 2 \times 10^5$ $1 \leq A_i \leq B_i \leq 10^9$ 输入中的所有数均为整数。$X_1, X_2, \cdots, X_N$ 的中位数定义如下。设 $x_1, x_2, \cdots, x_N$ 为将 $X_1, X_2, \cdots, X_N$ 按非降序排序后的结果。

若 $N$ 为奇数，则中位数为 $x_{(N+1)/2}$； 若 $N$ 为偶数，则中位数为 $(x_{N/2} + x_{N/2+1}) / 2$。如果 $X_1 = 1$ 且 $X_2 = 2$，中位数为 $\frac{3}{2}$；

如果 $X_1 = 1$ 且 $X_2 = 3$，中位数为 $2$；

如果 $X_1 = 2$ 且 $X_2 = 2$，中位数为 $2$；

如果 $X_1 = 2$ 且 $X_2 = 3$，中位数为 $\frac{5}{2}$。

因此，中位数可以取三个值：$\frac{3}{2}$、$2$ 和 $\frac{5}{2}$。

标签: AtCoder|abc169E

来源

AtCoder|abc169E