1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
| #include<bits/stdc++.h> #define fsb(a,b,c) for(int a=b;a<=c;a++) #define fbs(a,b,c) for(int a=b;a>=c;a--) using namespace std; int n=0,m,x,sz1=0,sz2=0; char s[10]; struct node1{ int x; }; struct node2{ int x; }; int operator<(node1 a,node1 b){ return a.x<b.x; } int operator<(node2 a,node2 b){ return a.x>b.x; } priority_queue<node1>s1; priority_queue<node2>s2; template<typename qw>inline void rll(qw &x){ qw f=1;x=0;char c=getchar(); while(!isdigit(c))f=c=='-'?-1:f,c=getchar(); while(isdigit(c))x=x*10+c-'0',c=getchar(); x*=f; } inline void add(int x){ if(s1.empty()){ s1.push((node1){x});sz1++;return; } if(x<=s1.top().x){ s1.push((node1){x});sz1++; if(sz1>sz2+1){ int t=s1.top().x;s1.pop(); s2.push((node2){t});sz1--;sz2++; } }else{ s2.push((node2){x});sz2++; if(sz2>sz1){ int t=s2.top().x;s2.pop(); s1.push((node1){t});sz1++;sz2--; } } } int main(){ rll(m); fsb(i,1,m){ rll(x);add(x); } rll(m); fsb(i,1,m){ scanf("%s",s+1); if(s[1]=='a'){ rll(x);add(x); }else{ printf("%d\n",s1.top().x); } } return 0; }
|