Maksimum u prozoru

Napisati generičku klasu max_prozor<T> koja održava maksimalni element u pokretnom prozoru fiksne veličine nad nizom elemenata tipa T. Klasa treba da podržava sledeće operacije:

Sve operacije treba da budu složenosti ne veće od $O(1)$ u amortizovanom vremenu.

Ulaz

Sa standardnog ulaza prvo se učitava veličina prozora $k$, a zatim, sve do kraja ulaza, i niz upita u formatu:

Izlaz

Na standardni izlaz ispisati rezultate izvršavanja naredbi m. Ako je prozor prazan, ispisati poruku izuzetka na standardni izlaz za greške.

Primer

stdin

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

stdout

2
3
4
4

Rešenje

main.cpp

#include <iostream>
#include <deque>
#include <vector>

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

			/* Dodaje element u prozor */
			void dodaj(const T& x)
			{
				// Ukloni elemente van prozora sa pocetka prozora
				if (!prozor.empty() &&
					 elementi.size() > velicina_prozora &&
					 elementi.size() - prozor.front() >= velicina_prozora
					) {
						prozor.pop_front();
				}

				// Ukloni elemente manje od x sa kraja prozora
				while (!prozor.empty() && elementi[prozor.back()] <= x) {
					prozor.pop_back();
				}

				// Dodaj novi element na kraj prozora
				elementi.push_back(x);
				prozor.push_back(elementi.size() - 1);
			}

			/* Vraca maksimalni element u prozoru */
			const T& max() const
			{
				if (prozor.empty()) {
					throw std::out_of_range("Prozor je prazan");
				}

				return elementi[prozor.front()];
			}

		private:
			std::vector<T> elementi;
			std::deque<int> prozor;
			size_t velicina_prozora;
	};
};

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

	matf::max_prozor<int> mp(k);

	char op;

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

	return 0;
}