SKS的SQL

Problem Description

SKS写了一个弱鸡SQL,这个SQL有一个特殊变量i,初值为0而且只有两种操作:

ADD (x): 把x存入SQL

GET: i=i+1,然后输出第i小的数

现在给你一个长为M的ADD操作序列A,N个时间点序列B,要求在每个B[i]时执行一次GET操作,求输出结果序列

Input

输入第一行有两个数字M, N
接下来是M个数字A(1), A(2), …, A(M)
再下来是N个数字B(1), B(2), …, B(N). 这N个数字已经从小到大排序过
本题数据范围均在int内
ADD和GET操作分别最多有3000次

Output

输出每个GET操作取出的值,一行一个值

Sample Input

Sample Output

Hint

共7个数 4个GET时间点
1时刻 加入3 序列为:3 同时执行一次GET操作 i=1 输出3
2时刻 加入1 序列为:1,3 同时执行一次GET操作 i=2 输出3
3时刻 加入-4 序列为:-4,1,3
4时刻 加入2 序列为:-4,1,2,3
5时刻 加入8 序列为:-4,1,2,3,8
6时刻 加入-1000 序列为:-1000,-4,1,2,3,8 先执行一次GET操作 i=3 输出1,再执行一次GET操作 i=4 输出2





首先思路比较明确就是模拟插入和查找的操作

因为要求是有序的,自然第一个想到的就是priority_queue

所以操起键盘就开干

由于priority_queue没有内置的输出函数

所以我们采用先出队后入队的方式



但是这个代码却Time Limit Exceeded了

原因自然是因为优先队列先出队后入队的操作

所以考虑采用vector

输入时便进行有序输入

同样采用对时间进行模拟的方式来进行输入和判断

时间缩短到了300ms不到


2019-06-11  00:12:18  Author: WindCry1



0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注