From 80ef8fb1f60a9591b77accc982001f58807ebc81 Mon Sep 17 00:00:00 2001
From: Anthony Wang
Date: Wed, 15 Jun 2022 19:49:12 -0500
Subject: Add 21.5 Open Gold catch.cpp

---
 21.5/open/gold/catch.cpp | 34 ++++++++++++++++++++++++++++++++++
 1 file changed, 34 insertions(+)
 create mode 100644 21.5/open/gold/catch.cpp

diff --git a/21.5/open/gold/catch.cpp b/21.5/open/gold/catch.cpp
new file mode 100644
index 0000000..002261a
--- /dev/null
+++ b/21.5/open/gold/catch.cpp
@@ -0,0 +1,34 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+const int MX = 1e5+5;
+
+int main() {
+	cin.tie(0)->sync_with_stdio(0);
+	int N; cin >> N;
+	vector<pair<ii, int>> A, C;
+	for (int i = 0; i < N; ++i) {
+		int q, t, x, n; cin >> q >> t >> x >> n;
+		if (q == 1) C.emplace_back(ii(t+x, t-x), n);
+		else A.emplace_back(ii(t+x, t-x), n);
+	}
+	sort(begin(A), end(A), [](auto & a, auto & b) { return a.f.s < b.f.s; });
+	sort(begin(C), end(C), [](auto & a, auto & b) { return a.f.s < b.f.s; });
+	set<pair<ii, int>> S;
+	int i = 0, ans = 0;
+	for (auto & a : A) {
+		while (i < C.size() && C[i].f.s <= a.f.s) S.insert(C[i++]);
+		int n = a.s;
+		while (n > 0 && S.size() && begin(S)->f.f <= a.f.f) {
+			auto c = *prev(S.upper_bound({ii(a.f.f, 1e9), 0}));
+			S.erase(c);
+			int x = min(n, c.s);
+			ans += x, n -= x;
+			if (x < c.s) S.emplace(c.f, c.s-x);
+		}
+	}
+	cout << ans;
+}
-- 
cgit v1.2.3-70-g09d2