HEADmaster

1 files changed, 30 insertions, 0 deletions

diff --git a/šola/aps1/dn/mediane/resitev.cpp b/šola/aps1/dn/mediane/resitev.cpp
new file mode 100644
index 0000000..32e6733
--- /dev/null
+++ b/šola/aps1/dn/mediane/resitev.cpp
@@ -0,0 +1,30 @@
+#include <iostream>
+#include <queue>
+using namespace std;
+int main (void) {
+	long N, m;
+	cin >> N;
+	priority_queue<long> l;
+	priority_queue<long> d;
+	for (long i = 0; i < N; i++) {
+		long r;
+		cin >> r;
+		if (i == 0) {
+			m = r;
+		} else if (r > m) {
+			d.push(-r);
+			l.push(m);
+		} else {
+			l.push(r);
+			d.push(-m);
+		}
+		if (d.size() > l.size()) {
+			m = -d.top();
+			d.pop();
+		} else if (l.size() > 0) {
+			m = l.top();
+			l.pop();
+		}
+		cout << m << endl;
+	}
+}