Half
题目描述
给定一个长度为 n 的整数二元组序列 $A=[(a_{1,0},a_{1,1}),(a_{2,0},a_{2,1}),\dots,(a_{n,0},a_{n,1})]$。
定义 w(l,r) 为区间 A[l,r] 中 2(r−l+1) 个数前一半小的数之和。
换句话说,w(l,r) 等于 $a_{l,0},a_{l,1},a_{l+1,0},a_{l+1,1},\dots,a_{r,0},a_{r,1}$ 中前 r−l+1 小的数之和。
对于每个 l,求 r=lminnw(l,r)。
输入格式
第一行一个正整数 n。
接下来 n 行,每行两个整数 ai,0,ai,1,表示序列中第 i 个二元组包含的两个元素。
输出格式
n 行每行一个整数,第 l 行的数表示 r=lminnw(l,r)。
样例 1
样例输入
6
5 6
3 4
-2 0
4 4
2 2
7 7
样例输出
1
-2
-2
4
2
7
解释
以 l=1 为例,从 r=1 开始逐位向右扩展:
| r |
第 r 个二元组 |
前 r 个二元组中前 r 小的数 |
w(1,r) |
| 1 |
5,6 |
{5} |
5 |
| 2 |
3,4 |
{3,4} |
7 |
| 3 |
−2,0 |
{−2,0,3} |
1 |
| 4 |
4,4 |
{−2,0,3,4} |
5 |
| 5 |
2,2 |
{−2,0,2,2,3} |
| 6 |
7,7 |
{−2,0,2,2,3,4} |
9 |
所以 l=1 的答案为 min(5,7,1,5,5,9)=1,在 r=3 处取得。
数据范围
-
子任务 1(3 分):n≤300;
-
子任务 2(5 分):n≤3000;
-
子任务 3(10 分):保证所有的 ai,j 均在 (−230,230) 内等概率均匀随机生成;
-
子任务 4(16 分):1≤ai,j≤1000。
-
子任务 5(32 分):n≤105。
-
子任务 6(34 分):无特殊限制。
对于 100% 的数据,1≤n≤5×105,∣ai,j∣<230。
样例附件