aboutsummaryrefslogtreecommitdiff
path: root/21.5/open/gold
diff options
context:
space:
mode:
Diffstat (limited to '21.5/open/gold')
-rw-r--r--21.5/open/gold/catch.cpp34
1 files changed, 34 insertions, 0 deletions
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;
+}