题目链接:http://poj.org/problem?id=3481
这题可以用set水过,用两个反向的set分别维护最大值和最小值即可(找最大值或最小值这里要用lower_bound
)。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
using namespace std;
const int INF=0x7fffffff;
struct C3 {
int p,k;
C3(int _p,int _k):p(_p),k(_k) {}
bool operator <(const C3& y) const {
return p<y.p;
}
};
struct C2 {
int p,k;
C2(int _p,int _k):p(_p),k(_k) {}
bool operator <(const C2& y) const {
return p>y.p;
}
};
set<C2> l2;
set<C3> l3;
int main() {
int op,k,p;
while(true) {
scanf("%d",&op);
set<C2>::iterator it2;
set<C3>::iterator it3;
if(op==0) break;
if(op==1) {
scanf("%d%d",&k,&p);
l2.insert(C2(p,k));
l3.insert(C3(p,k));
}
else if(op==2){
if(l2.size()==0) {
printf("0\n");
continue;
}
it2=l2.lower_bound(C2(INF,0));
int fp=(*it2).p;
printf("%d\n",(*it2).k);
it3=l3.find(C3(fp,0));
l2.erase(it2);
l3.erase(it3);
}
else if(op==3) {
if(l3.size()==0) {
printf("0\n");
continue;
}
it3=l3.lower_bound(C3(-1,0));
int fp=(*it3).p;
printf("%d\n",(*it3).k);
it2=l2.find(C2(fp,0));
l2.erase(it2);
l3.erase(it3);
}
}
}