双端队列+二分。
#include <cstdio>
#define MAXN 1000005
typedef struct {
int id;
int p;
} node_st;
node_st que[MAXN];
int rear = ,front = ;
void Insert(int id, int p) {
int l = front, r = rear, mid;
while ( l <= r) {
mid = (l+r)>>;
if (que[mid].p == p)
break;
if (que[mid].p < p)
l = mid+;
else
r = mid - ;
}
while (mid<rear && que[mid].p <= p)
++mid;
for (int i=rear-; i>=mid; --i)
que[i+] = que[i];
que[mid].id = id;
que[mid].p = p;
rear++;
}
int main() {
int c, id, p;
while (scanf("%d", &c)!=EOF && c) {
if (c == ) {
scanf("%d %d", &id, &p);
Insert(id, p);
} else {
if (rear == front)
printf("0\n");
else {
if (c == )
printf("%d\n", que[--rear].id);
else
printf("%d\n", que[front++].id);
}
}
}
return ;
}