- it
- PAT 1057 Stack (30 分)
#include <iostream>
#include <stack>
using namespace std
;
#define lowbit(i) ((i)&-(i))
const int maxn
=100010;
stack
<int> st
;
int c
[maxn
];
void update(int x
,int v
)
{
for(int i
=x
;i
<maxn
;i
+=lowbit(i
))
c
[i
]+=v
;
}
int getsum(int x
)
{
int sum
=0;
for(int i
=x
;i
>0;i
-=lowbit(i
))
sum
+=c
[i
];
return sum
;
}
void peekmedian()
{
int l
=1,r
=maxn
,mid
,k
=(st
.size()+1)/2;
while(l
<r
)
{
mid
=(l
+r
)/2;
if(getsum(mid
)>=k
)
r
=mid
;
else
l
=mid
+1;
}
printf("%d\n",l
);
}
int main()
{
int x
,n
;
string cmd
;
scanf("%d",&n
);
for(int i
=0;i
<n
;i
++)
{
cin
>>cmd
;
if(cmd
=="Push")
{
scanf("%d",&x
);
st
.push(x
);
update(x
,1);
}
else if(cmd
=="Pop")
{
if(st
.empty()==true)
printf("Invalid\n");
else
{
printf("%d\n",st
.top());
update(st
.top(),-1);
st
.pop();
}
}
else
{
if(st
.empty()==true)
printf("Invalid\n");
else
peekmedian();
}
}
return 0;
}
