MSE07B - Double Queue
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
#define ii pair<int, int>
#define iii pair<int, ii>
#define X first
#define Y second
const int maxK = 1000006;
using namespace std;
priority_queue<iii> heap_max;
priority_queue<iii, vector<iii>, greater<iii> > heap_min;
map<ii, int> M;
int cnt[maxK];
int main()
{
int type, k, p; iii e;
scanf("%d", &type);
while (type != 0) {
if (type == 1) {
scanf("%d %d\n", &k, &p);
cnt[k]++;
heap_min.push(iii(p, ii(k, cnt[k])));
heap_max.push(iii(p, ii(k, cnt[k])));
}
if (type == 2) {
if (heap_max.size() == 0) {printf("0\n");}
else {
do {
e = heap_max.top(); heap_max.pop();
k = e.Y.X;
} while (heap_max.size() && M.count(ii(k, e.Y.Y)) != 0);
if (M.count(ii(k, e.Y.Y)) != 0)
{printf("0\n");}
else {
M.insert(pair<ii, int> (ii(k, e.Y.Y), 1));
printf("%d\n", k);
}
}
}
if (type == 3) {
if (heap_min.size() == 0) {printf("0\n");}
else {
do {
e = heap_min.top(); heap_min.pop();
k = e.Y.X;
} while (heap_min.size() && M.count(ii(k, e.Y.Y)) != 0);
if (M.count(ii(k, e.Y.Y)) != 0)
{printf("0\n");}
else {
M.insert(pair<ii, int> (ii(k, e.Y.Y), 1));
printf("%d\n", k);
}
}
}
scanf("%d", &type);
}
return 0;
}