1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
}
|
