cses

commit 98229838ba23528f01047d769d9a44eac6552469
parent b80e63ba810301b05c973cf95caba956ec8c198a
Author: superpozycja <anna@superpozycja.net>
Date:   Wed, 30 Oct 2024 23:01:05 +0100

solve traffic lights

Diffstat:
A
sorting_and_searching/traffic_lights.cpp
 | 
50
++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 50 insertions(+), 0 deletions(-)
diff --git a/sorting_and_searching/traffic_lights.cpp b/sorting_and_searching/traffic_lights.cpp
@@ -0,0 +1,50 @@
+#include <bits/stdc++.h>
+
+using namespace std;
+
+using ui = unsigned int;
+using l = long;
+using ul = unsigned long;
+using ll = long long;
+using ull = unsigned long long;
+
+using vi = vector<int>;
+using vui = vector<ui>;
+using vl = vector<l>;
+using vul = vector<ul>;
+using vll = vector<ll>;
+using vull = vector<ull>;
+
+void solve()
+{
+	int x, n;
+	cin >> x >> n;
+	int res = x;
+	set<int> lights = { 0, x };
+	multiset<int> dists = { x };
+	int tmp;
+	for (int i = 0; i < n; i++) {
+		cin >> tmp;
+
+		auto it = lights.upper_bound(tmp);
+		auto it2 = it;
+		it2--;
+
+		dists.erase(dists.find(*it - *it2));
+		dists.insert(tmp - *it2);
+		dists.insert(*it - tmp);
+		lights.insert(tmp);
+
+		it = dists.end();
+		--it;
+		cout << *it << " ";
+	}
+	cout << "\n";
+}
+
+int main()
+{
+	ios::sync_with_stdio(0);
+	cin.tie(0);
+	solve();
+}