TopCoder

Thumb 100
tmwilliamlin
我的中文很爛

User's AC Ratio

82.6% (19/23)

Submission's AC Ratio

59.0% (82/139)

Tags

Description

維護一個多重集合
一開始為空集
支援下列兩個操作
1:插入一個數字
2:查詢當前第$\lceil \frac{集合大小}{2} \rceil$小的數(保證此時集合大小為奇數)

Input Format

一開始會有一個正整數$Q$,代表操作次數。
接著每行會是$1$ $x$或只有一個數字$2$,代表操作種類。
保證最後一個操作是第二種
輸入之整數保證是正的且$\leq 10^ 6$

Output Format

對於每次詢問輸出一行一個數字,代表答案。

Sample Input

7
1 5
1 7
1 3
2
1 8
1 6
2

Sample Output

5
6

Hints

本題共有三組測試資料。每組可有多個輸入檔案,全部答對該組才得分。

第一組19分,$Q\leq 10^ 3$
第二組30分,$Q\leq 10^ 6$
第三組51分,$Q\leq 10^ 7$
本題推薦以高度優化的方法讀入測資
可以參考 http://codepad.org/MMaoOXVi

Problem Source

rsabcmoi

Subtasks

For Testdata: 0 ~ 2, Score: 19
For Testdata: 0 ~ 5, Score: 30
For Testdata: 0 ~ 8, Score: 51
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 262144 262144
1 1000 262144 262144
2 1000 262144 262144
3 1000 262144 262144
4 1000 262144 262144
5 1000 262144 262144
6 5000 524288 262144
7 5000 524288 262144
8 5000 524288 262144