← 返回题目列表

AtCoder · abc169_e

E. 计数中位数

中文机器翻译题面 查看原题

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