UOJ Logo

NOI.AC

1S 512MB

#1296. 数据流中的第k大(2)

Statistics

题目描述

初始已有$n$个数字,有$m$次添加数字的操作,对于这$m$次操作的每一次输出原有数字、所有之前添加数字以及当前添加数字合并起来后的所有数字中的第$k$大。每次输出找到的第$k$大后,就从数字库中删除这个数字。

题目输入

第一行三个数字$n, m, k$。含义如上。

第二行$n$个数字,表示初始数字。

第三行$m$个数字,表示每次添加的数字。

题目输出

一行输出$m$个数字,表示每次添加数字后的所有数字的第$k$大数字。注意找到的这个数字会被删掉。

样例输出1

4 5 3

4 5 8 2

3 5 10 9 4

样例输出2

4 5 5 8 4

样例输入2

5 5 3

1 2 3 4 5

1 2 3 4 5

样例输出2

3 2 3 4 4

范围说明

对于50%的数据有:$ 1 \leq k \leq n \leq 10^3, 1 \leq m \leq 10^3$

对于100%的数据有:$1 \leq k \leq n \leq 10^5, 1 \leq m \leq 10^5$,所有数字都$ \leq 10^9$