Cod sursa(job #1307823)

Utilizator Corina1997Todoran Ana-Corina Corina1997 Data 2 ianuarie 2015 21:21:01
Problema Heapuri Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define NMax 200001

ifstream is("heapuri.in");
ofstream os("heapuri.out");

vector<int> d;
int type, x, n, k;

class Heap{
public:
    Heap(int n = 0) : nh(0), h(vector<int>(n + 1)), T(vector<int>(n + 1))
    {}
    void Push(int x)
    {
        h[++nh] = x; T[x] = nh;
        Up(x);
    }

    void Up(int x)
    {
        int f = T[x], t = f / 2;
        while ( t != 0 && d[h[f]] < d[h[t]] )
        {
            Swap(t, f);
            f = t; t = f / 2;
        }
    }
    void Pop(int x)
    {
        int t = T[x], f = 2 * t;
        Swap(t, nh--);

        while ( f <= nh )
        {
            if ( f + 1 <= nh && d[h[f + 1]] < d[h[f]] )
                f++;
            if ( d[h[f]] < d[h[t]] )
            {
                Swap(f, t);
                t = f;
                f = 2 * t;
            }
            else break;
        }
    }

    int Top() const
    {
        return h[1];
    }
private:
    void Swap(int f, int t)
    {
        swap(h[f], h[t]);
        T[h[t]] = t;
        T[h[f]] = f;
    }
    int nh;
    vector<int> h, T;
};


int main()
{

    is >> n;

    d = vector<int>(n + 1);
    Heap heap(n);

    for (int i = 1; i <= n; ++i)
    {
        is >> type;
        if ( type == 3 )
        {
            os << d[heap.Top()] << '\n';
            continue;
        }
        is >> x;
        if (type == 1)
        {
            d[++k] = x;
            heap.Push(k);
        }

        if ( type == 2 )
            heap.Pop(x);
    }

    is.close();
    os.close();
    return 0;
}