Cod sursa(job #1981754)

Utilizator MaligMamaliga cu smantana Malig Data 16 mai 2017 18:18:02
Problema Statistici de ordine Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream in("sdo.in");
ofstream out("sdo.out");

#define ll long long
#define pb push_back
const int NMax = 3e6 + 5;

int N,K,nrHeap;
int heap[NMax];

void sift(int);
void percolate(int);

int main() {
    in>>N>>K;
    for (int i=1;i <= N;++i) {
        int val;
        in>>val;

        if (nrHeap <= K) {
            heap[++nrHeap] = val;
            percolate(nrHeap);
        }
        else {
            heap[1] = val;
            sift(1);
        }
    }


    swap(heap[1],heap[nrHeap]);
    --nrHeap;

    sift(1);

    out<<heap[1]<<' ';

    in.close();out.close();
    return 0;
}

void sift(int node) {

    int son = 0;
    do {
        son = 0;
        int fs = node*2,
            ss = node*2 + 1;
        if (fs <= nrHeap) {
            son = fs;
            if (ss <= nrHeap && heap[ss] > heap[son]) {
                son = ss;
            }
        }

        if (son && heap[son] > heap[node]) {
            swap(heap[node],heap[son]);
            node = son;
        }
        else {
            son = 0;
        }
    }
    while (son);
}

void percolate(int node) {

    int dad = node/2;
    while (node != 1 && heap[node] > heap[dad]) {
        swap(heap[node],heap[dad]);
        node = dad;

        dad = node/2;
    }
}