良心出题人黄队

题目描述
为了体现平均难度, 我们认为一场比赛的平均难度可以用所有题目通过人数的中位数表示。如果不知道什么是中位数，参见提示。如果一道题的通过人数大于等于中位数, 我们就认为这道题的难度不超过这场比赛的平均难度。

现在，Xryjr233 得到了整场比赛的所有提交记录。这些记录一共有 \(n\) 条, 每一条用两个非负整数 \(a,b\) 表示。

\(a\) 表示这次提交的题目的题号，由于这些题需要保密, 所以题号都是经过加密的, 不仅很大, 而且不一定连续。

\(b\) 是 \(0\) 或 \(1\),\(0\) 表示这次提交没有通过，\(1\) 表示这次提交通过了。

这件事对于 Xryjr233 太难了, 于是要你帮助他。

简化题意：

给出 \(n\) 个数对, 形如 \((a_i,b_i)\)，不计入所有 \(b_i=0\) 的数对 \(i\)，求所有 \(a_i\) 出现次数的中位数。

注意: 如果一个 \(ai\) 在读入数对中出现，但是最终统计出现次数为 \(0\)，依然影响中位数的计算。具体见下例

例如 \(9\) 个数对 \((1,1),(3,0),(5,1),(3,0),(1,1),(1,0),(1,1),(5,1),(3,0)\):

排除 \(b_i=0\) 的数对得到 \((1,1),(5,1),(1,1),(1,1),(5,1)\);

其中 \(1,3,5\) 的出现次数为 \(3,0,2\)（注意 \(3\) 的出现次数为 \(0\)，但是依然参与了计算）；

这个数列的中位数为 \(2\)，所以答案为 \(2\)。

输入输出格式
输入格式
第一行输入一个正整数 \(n\)，表示数对数量。

接下来 \(n\) 行，第 \(i+1\) 行两个非负整数 \(a_i,b_i\), 表示一个数对。

输出格式
输出一个整数 \(ans\)，表示不统计 \(b_i=0\) 的数对 \(i,a_i\) 出现次数的中位数乘 \(2\) 的结果。

样例
样例 1

9
1 1
3 0
5 1
3 0
1 1
1 0
1 1
5 1
3 0

4

样例 2

7
1919810 1
233 0
233 1
666 1
114514 1
114514 1
1919810 1

3

样例解释
第一个样例就是题目中的例子，乘 2 结果为 4。

第二个样例去除 bi=0 的数对后得到 \((1919810,1),(233,1),(666,1),(114514,1),(114514,1),(1919810,1)\)。

四个数的出现次数分别为$ 2,1,1,2$, 中位数为 \(1.5\)，乘 2 结果为 3。

限制
此题有 10 个测试点, 每个点都为 10 分。

对于所有数据，\(1≤n≤10^6,1≤a_i≤10^{18},b_i=0,1\)，所有数均为整数。

对于第 1 个测试点，所有 \(b_i=0\);

对于第 2,3 个测试点，\(n≤10,a_i≤100\)；

对于第 4,5 个测试点，\(n≤10^3,a_i≤10^5\)；

对于第 6,7 个测试点，\(n≤10^3,a_i≤10^9\)；

对于第 8,9 个测试点，\(n≤10^5,a_i≤10^9\)；

对于第 10 个测试点，\(n≤10^6,a_i≤10^{18}\)。

时空限制：2s,512MB
提示
中位数的计算:

对于一组数据 \(a_1,a_2,\cdots,a_n\), 我们将它排序后得到 \(b_1,b_2,\cdots,b_n\)。

对于$ n$ 为奇数，中位数为 \(b_{\tfrac{n+1}{2}}\), 即数列中间的那个数。

对于 \(n\) 为偶数，中位数为 \(\tfrac{1}{2}(b_{\tfrac{n}{2}}+b_{\tfrac{n+2}{2}})\)，即数列中间两个数的平均数。

既然要数数，就要处理一下。所以先把所有数离散化。然后按照题目，排序，数数，求出b数组，排完序后求中位数就可以了。

#include
using namespace std;
const int N=1e6+5;
int n,m,x,y,a[N],v[N],t[N],k;
long long lsh[N];
struct node{
	long long a;
	int b;
}p[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&p[i].a,&p[i].b),lsh[i]=p[i].a;
	sort(lsh+1,lsh+n+1);
	for(int i=1;i<=n;i++)
	{
		k=lower_bound(lsh+1,lsh+n+1,p[i].a)-lsh;
		v[k]=1;
		if(p[i].b)
			t[k]++;
	}
	for(int i=1;i<=n;i++)
		if(v[i])
			a[++m]=t[i];
	sort(a+1,a+m+1);
	if(m&1)
		printf("%d",a[m/2+1]<<1);
	else
		printf("%d",a[m/2]+a[m/2+1]);
	return 0;
}