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;
}

Download