Medijana prozora

Napisati genericku klasu medijana_prozor<T> koja implementira strukturu podataka koja podržava sledeće operacije nad prozorom fiksne veličine:

medijana_prozor(size_t k) - konstruktor koji kreira prazan prozor maksimalne veličine k.
void dodaj(const T& vrednost) - dodaje novu vrednost u prozor. Ukoliko je prozor već pun, najstarija vrednost se uklanja iz prozora.
T medijana() const - vraća medijanu vrednosti u prozoru. Ukoliko je broj elemenata u prozoru neparan, medijana je srednji element kada su elementi sortirani. Ukoliko je broj elemenata paran, medijana je aritmetička sredina dva srednja elementa.

Funkcija medijana treba da radi u vremenskoj složenosti $O(1)$, dok funkcija dodaj treba da radi u amortizovanoj vremenskoj složenosti $O(\log k)$, gde je k veličina prozora.

Ulaz

Sa standardnog ulaza se učitava veličina prozora k, a zatim, sve do kraja ulaza, naredbe u formatu:

a x - dodaje vrednost x (vrednost u pokretnom zarezu) u prozor.
m - ispisuje medijanu trenutnog prozora.

Izlaz

Na standardni izlaz ispisati rezultate izvršavanja naredbi m. Ukoliko je prozor prazan ili nije pun, treba baciti izuzetak std::out_of_range sa odgovarajućom porukom.

Primer

`stdin`

5
a 1
m
a 3
a 5
a 7
a 9
m
a 3
a 3
a 4
m

`stdout`

5
4

`stderr`

Prozor nije pun

Primer

`stdin`

4
a 1
a 2
a 3
a 1
m
a 4
a 3
m

`stdout`

1.5
3

Rešenje

`main.cpp`

#include <iostream>
#include <queue>
#include <unordered_map>

namespace matf
{
	/* Klasa za median u prozor */
	template <typename T>
	class medijana_prozor
	{
		public:
			/* Inicijalizacija prozora sa zadatom velicinom */
			medijana_prozor(size_t velicina) : velicina_prozora(velicina) {}

			/* Dodaje element u prozor */
			void dodaj(const T& x)
			{
				// Uklanjanje starog elementa ako je prozor pun
				if (prozor.size() == velicina_prozora) {
					ukloni();
				}

				// Dodavanje novog elementa
				prozor.push(x);
				if (min_heap.empty() || x >= min_heap.top()) {
					min_heap.push(x);
					velicina_min++;
				} else {
					max_heap.push(x);
					velicina_max++;
				}

				balansiraj();

				lenjo_ciscenje();
			}

			/* Vraca medijanu prozora */
			T medijana() const
			{
				if (prozor.size() != velicina_prozora) {
					throw std::out_of_range("Prozor nije pun");
				}

				// Neparan broj elemenata
				if (velicina_min > velicina_max) {
					return min_heap.top();
				} else if (velicina_max > velicina_min) {
					return max_heap.top();
				}

				// Paran broj elemenata
				return (max_heap.top() + min_heap.top()) / 2;
			}

		private:
			/* Balansira velicine heap-ova */
			void balansiraj()
			{
				if (velicina_min > velicina_max + 1) {
					max_heap.push(min_heap.top());
					min_heap.pop();
					velicina_min--;
					velicina_max++;
				} else if (velicina_max > velicina_min + 1) {
					min_heap.push(max_heap.top());
					max_heap.pop();
					velicina_max--;
					velicina_min++;
				}
			}

			/* Uklanja najstariji element iz prozora */
			void ukloni()
			{
				T stari = prozor.front();
				prozor.pop();

				// Oznacavanje za uklanjanje
				brojac_uklanjanja[stari]++;

				// Uklanjanje iz odgovarajuceg heap-a
				if (!max_heap.empty() && stari <= max_heap.top()) {
					velicina_max--;
				} else if (!min_heap.empty() && stari >= min_heap.top()) {
					velicina_min--;
				}
			}

			/* Lenjo ciscenje heap-ova */
			void lenjo_ciscenje()
			{
				while (!max_heap.empty() && brojac_uklanjanja[max_heap.top()] > 0) {
					brojac_uklanjanja[max_heap.top()]--;
					max_heap.pop();
				}

				while (!min_heap.empty() && brojac_uklanjanja[min_heap.top()] > 0) {
					brojac_uklanjanja[min_heap.top()]--;
					min_heap.pop();
				}
			}


		private:
			// Dodatne strukture podataka potrebne za racunanje mediana
			std::priority_queue<T> max_heap;
			std::priority_queue<T, std::vector<T>, std::greater<T>> min_heap;
			std::queue<T> prozor;
			std::unordered_map<T, unsigned int> brojac_uklanjanja;
			size_t velicina_max = 0;
			size_t velicina_min = 0;
			size_t velicina_prozora;
	};
};

int main(void)
{
	size_t k; std::cin >> k;

	matf::medijana_prozor<double> mp(k);

	char op;

	while (std::cin >> op) {
		if (op == 'a') {
			double x; std::cin >> x;
			mp.dodaj(x);
		} else if (op == 'm') {
			try {
				std::cout << mp.medijana() << std::endl;
			} catch (const std::out_of_range& e) {
				std::cerr << e.what() << std::endl;
			}
		}
	}

	return 0;
}