Cod sursa(job #2577749)

Utilizator TzigCurta Tudor Tzig Data 9 martie 2020 19:54:15
Problema Statistici de ordine Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>

using namespace std;

ifstream f("sdo.in");
ofstream g("sdo.out");

const int NMAX = 3000005;

int N,K;
int X[NMAX];
int M;

void Upheap(int nod)
{
    int tata=nod/2;
    if(tata && X[tata]>X[nod]){
        swap(X[tata],X[nod]);
        Upheap(tata);
    }
}

void Downheap(int nod)
{
    if(nod*2<=M && 2*nod+1>M){
        if(X[2*nod]<X[nod]){
            swap(X[2*nod],X[nod]);
        }
    }else{
        if(2*nod+1<=M){
            int minim;
            if(X[2*nod]<X[2*nod+1]){
                minim=2*nod;
            }else{
                minim=2*nod+1;
            }
            if(X[minim]<X[nod]){
                swap(X[minim],X[nod]);
                Downheap(minim);
            }
        }
    }
}

void Inserare(int val)
{
    X[++M]=val;
    Upheap(M);
}

void Sterge()
{
    X[1]=X[M];
    M--;
    Downheap(1);
}

int main()
{
    f>>N>>K;
    for(int i=1;i<=N;i++){
        int a;
        f>>a;
        Inserare(a);
    }
    K--;
    while(K){
        Sterge();
        K--;
    }
    g<<X[1];
    f.close();
    g.close();
    return 0;
}