666 . 鵝老師的教室

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

80.0% (8/10)

Tags

apcsc apcsc-ds

Description

APCSC 請了一位鵝老師來給大家上課。鵝老師很喜歡點名，而且很過分的是，牠點名會看著成績單，直接講出那位同學的總分。鵝老師很懶惰，牠手上的成績單由分數低到高排序，然後牠只會唸最低的那兩個分數而已 (如果最低分有兩個，它就是最低分跟第二低分)。這會產生幾個事件。

  • 鵝老師講出了最低的分數
  • 鵝老師講出了第二低的分數
  • 分數最低的同學停修了
  • 有新同學帶著他的成績加入

請幫忙模擬出鵝老師的教室情況。

Input Format

輸入第一行有兩個正整數 $N, M (1 \leq N \leq 10^ 6, 1 \leq M \leq 10^ 4, M < N)$，$N$ 代表教室原本的學生數，$M$ 代表發生的事件數。
第二行有 $N$ 個數字 $a_{i} (0 \leq a_{i} \leq 10^ 9)$，代表第 $i$ 位同學的總分。
第三行以後共有 $M$ 行指令，指令的格式如下：

  • 0，輸出教室內的同學的最低分
  • 1，輸出教室內的同學的第二低分
  • 2，移除教室內的同學的最低分 (如果重複，移除其中一個即可)
  • 3 a，新增一個分數為 a 的同學進教室 $(0 \leq a \leq 10^ 9)$

註：請用輸入優化

Output Format

請依照指令輸出同學的分數，分數之間用換行分隔。

Sample Input 1

6 5
1 2 3 4 5 6
0
2
1
3 2
1

Sample Output 1

1
3
2

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~8 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
Submit
Back to Top