分数: 500 点
问题陈述
有 N 整数 X_1, X_2, \cdots, X_N,我们知道 A_i \leq X_i \leq B_i。 找出中位数不同的值的数量 X_1, X_2, \cdots, X_N 可以服用。
注释
的中位数 X_1, X_2, \cdots, X_N 定义如下。让 x_1, x_2, \cdots, x_N 是排序的结果 X_1, X_2, \cdots, X_N 按升序排列。
- If N 为奇数,中位数为 x_{(N+1)/2};
- if N 是偶数,中位数是 (x_{N/2} + x_{N/2+1}) / 2.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq B_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 B_1 A_2 B_2 : A_N B_N
输出
打印答案。
示例输入 1
2 1 2 2 3
示例输出 1
3
-
If X_1 = 1 和 X_2 = 2,中位数是 \frac{3}{2};
-
if X_1 = 1 和 X_2 = 3,中位数是 2;
-
if X_1 = 2 和 X_2 = 2,中位数是 2;
-
if X_1 = 2 和 X_2 = 3,中位数是 \frac{5}{2}.
因此,中位数可以取三个值: \frac{3}{2}, 2,和 \frac{5}{2}.
示例输入 2
3 100 100 10 10000 1 1000000000
示例输出 2
9991