You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
64 lines
1.4 KiB
64 lines
1.4 KiB
#include<iostream>
|
|
#include<algorithm>
|
|
#include<cstring>
|
|
|
|
using namespace std;
|
|
|
|
const int N = 100010;
|
|
int h[N], hp[N], ph[N], cnt;
|
|
|
|
void heap_swap(int a, int b) {
|
|
swap(ph[hp[a]], ph[hp[b]]);
|
|
swap(hp[a], hp[b]);
|
|
swap(h[a], h[b]);
|
|
}
|
|
|
|
void down(int u) {
|
|
int t = u;
|
|
if (u * 2 <= cnt && h[u * 2] < h[t])t = u * 2;
|
|
if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t])t = u * 2 + 1;
|
|
if (u != t) {
|
|
heap_swap(u, t);
|
|
down(t);
|
|
}
|
|
}
|
|
|
|
void up(int u) {
|
|
while (u / 2 && h[u] < h[u / 2]) {
|
|
heap_swap(u, u / 2);
|
|
u >> 1;
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
ios::sync_with_stdio(false);
|
|
int n, m = 0;
|
|
cin >> n;
|
|
while (n--) {
|
|
char op[5];
|
|
int k, x;
|
|
cin >> op;
|
|
if (!strcmp(op, "I")) {
|
|
cin >> x;
|
|
ph[++m] = ++cnt, hp[cnt] = m, h[cnt] = x;
|
|
up(cnt);
|
|
} else if (!strcmp(op, "PM"))printf("%d\n", h[1]);
|
|
else if (!strcmp(op, "DM")) {
|
|
heap_swap(1, cnt);
|
|
cnt--;
|
|
down(1);
|
|
} else if (!strcmp(op, "D")) {
|
|
cin >> k;
|
|
k = ph[k];
|
|
heap_swap(k, cnt);
|
|
cnt--;
|
|
down(k), up(k);
|
|
} else {
|
|
cin >> k >> x;
|
|
k = ph[k];
|
|
h[k] = x;
|
|
down(k), up(k);
|
|
}
|
|
}
|
|
return 0;
|
|
} |