優先列二つの山のメンテナンス
1827 ワード
ニャンコ1073
説明
N個の数、M回のクエリーを入力します.
クエリーごとに数xが与えられます.
要求:毎回照会出力前のx個数のうち、i番目に小さい数.(iは第i回クエリー)
あなたはMを仮定することができます <= N,Xi<=Xi+1<=Xi+2<=….<=Xm(=N)
入力
Line 0:T
Line 1:N,M
Line 2…LineN+1:num 1、…、numN
Linen+2…LineN+2+M:x 1、…、xM
N<30000,num<20000000
出力
毎回照会出力前のiの小さい数は、単独の行です.
詳細なフォーマットはサンプルを参照してください.
サンプル入力
説明
N個の数、M回のクエリーを入力します.
クエリーごとに数xが与えられます.
要求:毎回照会出力前のx個数のうち、i番目に小さい数.(iは第i回クエリー)
あなたはMを仮定することができます <= N,Xi<=Xi+1<=Xi+2<=….<=Xm(=N)
入力
Line 0:T
Line 1:N,M
Line 2…LineN+1:num 1、…、numN
Linen+2…LineN+2+M:x 1、…、xM
N<30000,num<20000000
出力
毎回照会出力前のiの小さい数は、単独の行です.
詳細なフォーマットはサンプルを参照してください.
サンプル入力
1
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
サンプル出力3
3
1
2
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
struct cmp{
bool operator ()(int x,int y){
return x>y;
}
};
int main(){
int T;
cin>>T;
while(T--){
int n,m;
cin>>n>>m;
int a[n+1];
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
priority_queue<int> big; // ,top i
priority_queue<int,vector<int>,cmp > small; // , i
int num;
int count=1;
int t;
for (int i=1;i<=m;i++){
scanf("%d",&num);
while(count<=num){ // num
if (big.size()<i){ // i, ,
// top , , ,
//
if (small.size()==0) {
big.push(a[count]);
count++;
continue;
}
if (a[count]>small.top()){
t=small.top();
small.pop();
small.push(a[count]);
big.push(t);
}
else big.push(a[count]);
}
else {
if (a[count]<big.top()){
t=big.top();
big.pop();
big.push(a[count]);
small.push(t);
}
else small.push(a[count]);
}
count++;
}
if (big.size()<i){ // big i ,
t=small.top();
small.pop();
big.push(t);
}
cout<<big.top()<<endl;
}
}
}