| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 365859 | Kazalika | Two Dishes (JOI19_dishes) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast, no-stack-protector, unroll-loops, fast-math")
#pragma GCC target("sse, sse2, sse3, ssse3, sse4.1, sse4.2, popcnt, abm, avx, mmx, tune=native")
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
const ll inf = 1e18;
ll sgt[N << 2], add[N << 2];
void push(int t, int l, int r) {
if (add[t]) {
sgt[t] += add[t];
if (l < r) {
add[t << 1] += add[t];
add[t << 1 | 1] += add[t];
}
add[t] = 0;
}
}
void upd(int t, int l, int r, int x, ll val) {
push(t, l, r);
if (x < l || x > r)
return;
if (l == r) {
sgt[t] = max(sgt[t], val);
return;
}
int md = (l + r) >> 1;
upd(t << 1, l, md, x, val);
upd(t << 1 | 1, md + 1, r, x, val);
sgt[t] = max(sgt[t << 1], sgt[t << 1 | 1]);
}
void add_range(int t, int l, int r, int x, int y, ll val) {
push(t, l, r);
if (l > y || r < x || l > r)
return;
if (l >= x && r <= y) {
add[t] = val;
push(t, l, r);
return;
}
int md = (l + r) >> 1;
add_range(t << 1, l, md, x, y, val);
add_range(t << 1 | 1, md + 1, r, x, y, val);
sgt[t] = max(sgt[t << 1], sgt[t << 1 | 1]);
}
ll get_max(int t, int l, int r, int x, int y) {
push(t, l, r);
if (l > y || r < x || l > r)
return -inf;
if (l >= x && r <= y)
return sgt[t];
int md = (l + r) >> 1;
return max(get_max(t << 1, l, md, x, y), get_max(t << 1 | 1, md + 1, r, x, y));
}
int a[N], b[N];
ll s[N], t[N];
int p[N], q[N];
ll sa[N], sb[N];
map<pair<int, int>, ll> qq;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> a[i] >> s[i] >> p[i];
sa[i] = (i ? sa[i - 1] : 0) + a[i];
}
for (int i = 0; i < m; ++i) {
cin >> b[i] >> t[i] >> q[i];
sb[i] = (i ? sb[i - 1] : 0) + b[i];
}
ll sum = 0;
for (int i = 0; i < n; ++i) {
if (sa[i] > s[i])
continue;
if (sa[i] + sb[m - 1] <= s[i])
sum += p[i];
else {
int nw = upper_bound(sb, sb + m, s[i] - sa[i]) - sb;
qq[{(i + 1) - 1, -nw - 1}] += p[i];
}
}
for (int i = 0; i < m; ++i) {
if (sb[i] > t[i])
continue;
if (sb[i] + sa[n - 1] <= t[i])
sum += q[i];
else {
int nw = upper_bound(sa, sa + n, t[i] - sb[i]) - sa;
sum += q[i];
qq[{nw, -(i + 1)}] -= q[i];
}
}
for (auto &pt : qq) {
int y = -pt.first.second;
ll val = pt.second;
ll nw = get_max(1, 0, N - 1, 0, y - 1);
upd(1, 0, N - 1, y, nw);
add_range(1, 0, N - 1, 0, y - 1, val);
}
push(0, 0, N - 1);
ll ans = sgt[1] + sum;
cout << ans;
}