UVa 10107 - What is the Median?

// UVa 10107 - What is the Median?

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

#define datatype long long int

class comp1 {
public:
	bool operator()(const datatype & a, const datatype & b) {
		return a < b;
	}
};

class comp2 {
public:
	bool operator()(const datatype & a, const datatype & b) {
		return a > b;
	}
};

int main() {
	datatype v;
	priority_queue<datatype, vector<datatype>, comp1> left;
	priority_queue<datatype, vector<datatype>, comp2> right;
	while (cin >> v) {
		// insert in heaps
		if (left.empty() || v < left.top()) {
			left.push(v);
		} else if (right.empty() || v > right.top()) {
			right.push(v);
		} else if (left.size() <= right.size())
			left.push(v);
		else
			right.push(v);
		// balance heaps
		if (left.size() > 1 + right.size()) {
			right.push(left.top());
			left.pop();
		} else if (right.size() > left.size() + 1) {
			left.push(right.top());
			right.pop();
		}
		// calc medians
		if (left.size() > right.size())
			cout << left.top();
		else if (right.size() > left.size()) {
			cout << right.top();
		} else
			cout << (left.top() + right.top()) / 2;
		cout << endl;
	}

	return 0;
}