Cod sursa(job #2555868)

Utilizator topala.andreiTopala Andrei topala.andrei Data 24 februarie 2020 14:19:37
Problema Statistici de ordine Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <queue>
#define MAXN 3000001

using namespace std;

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

int N, K, v[MAXN];
struct number_in_heap {
	int position, value;

	number_in_heap(int pos, int val) {
		position = pos;
		value = val;
	}
	inline bool operator < (const number_in_heap &x) const {
		return value > x.value;
	}
};

bool cmp(int a, int b) {
	return a > b;
}
void read() {
	f >> N >> K;
	for (int i = 1; i <= N; ++i) {
		f >> v[i];
	}
	make_heap(v + 1, v + N + 1, cmp);
}
// O(n + klogk) - solution
int solve_heap_bfs() {
	priority_queue <number_in_heap> Q;

	Q.push(number_in_heap(1, v[1]));
	for (int i = 1; i < K; ++i) {
		number_in_heap aux = Q.top();
		Q.pop();
		if (2 * aux.position <= N) {
			number_in_heap tmp = number_in_heap(2 * aux.position, v[2 * aux.position]);

			Q.push(tmp);
		}
		if (2 * aux.position + 1 <= N) {
			number_in_heap tmp = number_in_heap(2 * aux.position + 1, v[2 * aux.position + 1]);

			Q.push(tmp);
		}
	}
	return Q.top().value;
}
int main() {
	read();
	g << solve_heap_bfs();
	return 0;
}