vector insert 不是 $O(size)$ 的嘛
by yinhee @ 2023-10-07 19:56:54
@[yinhee](/user/578590)
```cpp
#include<bits/stdc++.h>
#include<queue>
using namespace std;
typedef long long ll;
ll t;
ll x;
ll cnt,sz1,sz2;
int main(){
ios::sync_with_stdio(0);
cin>>t;
while(t--){
priority_queue<ll,vector<ll>,less<ll> > pq1;//<min 5 4 3 2 1
priority_queue<ll,vector<ll>,greater<ll> > pq2;//>min 6 7 8 9 10
cnt=sz1=sz2=0;
while(1){
cin>>x;
if(!x)break;
if(x!=-1){
cnt++;
if(pq2.size()&&x>pq2.top())pq2.push(x),sz2++;
else pq1.push(x),sz1++;
while(sz1>(cnt+1)/2&&pq1.size()){
pq2.push(pq1.top());
pq1.pop();
sz1--;
sz2++;
}
while(sz2>cnt/2&&pq2.size()){
pq1.push(pq2.top());
pq2.pop();
sz1++;
sz2--;
}
}
else{
cout<<pq1.top()<<'\n';
pq1.pop();
sz1--;
cnt--;
while(sz1>(cnt+1)/2&&pq1.size()){
pq2.push(pq1.top());
pq1.pop();
sz1--;
sz2++;
}
while(sz2>cnt/2&&pq2.size()){
pq1.push(pq2.top());
pq2.pop();
sz1++;
sz2--;
}
}
}
}
return 0;
}
```
那这个呢
by Iwara @ 2023-10-07 20:05:45