TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

85.9% (85/99)

Submission's AC Ratio

44.7% (195/436)

Tags

Description

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

Input Format

一開始會有一個正整數$Q$,代表操作次數。
接著每行會是$1$ $x$或只有一個數字$2$,代表操作種類。

輸入之整數保證是正的且$\leq 10^ 6$

Output Format

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

Sample Input 1

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

Sample Output 1

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

No. Testdata Range Score
1 0~2 19
2 0~5 30
3 0~8 51

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1 2 3
1 1000 262144 262144 1 2 3
2 1000 262144 262144 1 2 3
3 1000 262144 262144 2 3
4 1000 262144 262144 2 3
5 1000 262144 262144 2 3
6 5000 524288 262144 3
7 5000 524288 262144 3
8 5000 524288 262144 3