cses

commit 2f48640061f1abd2b4726dd379d79a6c8bbe7a9d
parent 923a8eac8082917113e3b982742ff4bf62ffdb55
Author: superpozycja <anna@superpozycja.net>
Date:   Mon, 11 Nov 2024 19:18:23 +0100

solve sliding window median

Diffstat:
A
sorting_and_searching/sliding_window_median.cpp
 | 
55
+++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 55 insertions(+), 0 deletions(-)
diff --git a/sorting_and_searching/sliding_window_median.cpp b/sorting_and_searching/sliding_window_median.cpp
@@ -0,0 +1,55 @@
+#include <bits/stdc++.h>
+#include <ext/pb_ds/tree_policy.hpp>
+#include <ext/pb_ds/assoc_container.hpp>
+ 
+using namespace std;
+namespace __gnu_pbds{
+	template<class T>
+         using ordered_multiset = tree<T,
+                       null_type,
+                       less_equal<T>,
+                       rb_tree_tag,
+                       tree_order_statistics_node_update>;
+}
+using namespace __gnu_pbds;
+
+
+using ui = unsigned int;
+using ul = unsigned long;
+using ll = long long;
+using ull = unsigned long long;
+
+using vi = vector<int>;
+using vui = vector<ui>;
+using vl = vector<long>;
+using vul = vector<ul>;
+using vll = vector<ll>;
+using vull = vector<ull>;
+
+void solve()
+{
+	int n, k;
+	cin >> n >> k;
+	ordered_multiset<int> s;
+	queue<int> q;
+	for (int i = 0; i < n; i++) {
+		int x;
+		cin >> x;
+		s.insert(x);
+		q.push(x);
+		if (i >= k - 1) {
+			cout <<  *(s.find_by_order((k-1)/2)) << " ";
+			int p = q.front();
+			s.erase(s.find_by_order(s.order_of_key(p)));
+			q.pop();
+		}
+	}
+	cout << "\n";
+}
+
+int main()
+{
+	ios::sync_with_stdio(0);
+	cin.tie(0);
+	solve();
+}