Cod sursa(job #2738345)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 5 aprilie 2021 18:37:17
Problema Heapuri Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin( "heapuri.in" );
ofstream fout( "heapuri.out" );

const int NMAX = 200005;

class heap {
private:
    int v[NMAX];
    int idx[NMAX];
    bool to_delete[NMAX];

    const int INF = 2000000001;
    int lg = 0;

    void upheap( int p ) {
        while( p > 1 && v[p / 2] > v[p] ) {
            swap( v[p], v[p / 2] );
            swap( idx[p], idx[p / 2] );
            p /= 2;
        }
    }
    void downheap( int p ) {
        if( p * 2 > lg ) return;

        int val1, val2;

        val1 = v[p * 2];
        if( val2 * 2 + 1 > lg ) val2 = INF;
        else val2 = v[p * 2 + 1];

        if( min( val1, val2 ) > v[p] ) return;

        if( val1 < val2 ) {
            swap( v[p], v[p * 2] );
            swap( idx[p], idx[p * 2] );
            downheap( p * 2 );
        }
        else {
            swap( v[p], v[p * 2 + 1] );
            swap( idx[p], idx[p * 2 + 1] );
            downheap( p * 2 + 1 );
        }
    }
public:
    void h_insert( int x, int idxt ) {
        v[++lg] = x;
        idx[lg] = idxt;

        upheap( lg );
    }
    void h_delete( int idxt ) {
        to_delete[idxt] = true;

        while( to_delete[ idx[1] ] ) {
            swap( v[1], v[lg] );
            swap( idx[1], idx[lg] );

            --lg;
            downheap( 1 );
        }
    }
    int h_top() {
        return v[1];
    }
    void printheap() {
        fout << lg << '\n';
        for( int i = 1; i <= lg; ++i )
            fout << v[i] << ' ';
        fout << '\n';
    }
};

heap H;

int main()
{
    int N;
    int t, x;
    int nr_el = 0;

    fin >> N;
    for( int i = 1; i <= N; ++i ) {
        fin >> t;

        if( t == 1 ) {
            fin >> x;

            H.h_insert( x, ++nr_el );
        }
        if( t == 2 ) {
            fin >> x;

            H.h_delete( x );
        }
        if( t == 3 )
            fout << H.h_top() << '\n';
    }

    return 0;
}