#1992. Half

    ID: 1992 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest4599来源:qoj.ac数据:公开样例二分答案

Half

Half

题目描述

标题: Half - Problem - QOJ.ac

#21431. Half

Statistics

The problem was used in the following contests:

题目描述

给定一个长度为 n 的整数二元组序列 A=[(a1,0,a1,1),(a2,0,a2,1),…,(an,0,an,1)]。

定义 w(l,r) 为区间 A[l,r] 中 2(r−l+1) 个数前一半小的数之和。

换句话说,w(l,r) 等于 al,0,al,1,al+1,0,al+1,1,…,ar,0,ar,1 中前 r−l+1 小的数之和。

对于每个 l,求 minr=lnw(l,r)。

输入格式

第一行一个正整数 n。

接下来 n 行,每行两个整数 ai,0,ai,1,表示序列中第 i 个二元组包含的两个元素。

输出格式

n 行每行一个整数,第 l 行的数表示 minr=lnw(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} 5 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。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

6
5 6
3 4
-2 0
4 4
2 2
7 7
1
-2
-2
4
2
7