diff options
| -rw-r--r-- | 21.5/open/gold/catch.cpp | 34 |
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; +} |