Submission #1173926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173926		1bin	Two Dishes (JOI19_dishes)	C++20	100 / 100	4269 ms	158788 KiB

dishes

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int b = 1<<20;
const ll inf = 1e18;
ll n, m, A[b], S[b], P[b], sumA[b], sumB[b];
ll B[b], T[b], Q[b];
ll seg[b * 2], ADD[b * 2], MX[b * 2];

void upd_lazy(int ix, int l, int r) {
    if (ADD[ix]) {
        seg[ix] += ADD[ix];
        if (l != r) {
            ADD[ix * 2] += ADD[ix];
            ADD[ix * 2 + 1] += ADD[ix];
            MX[ix * 2] += ADD[ix];
            MX[ix * 2 + 1] += ADD[ix];
        }
        ADD[ix] = 0;
    }
    if (MX[ix] > -inf) {
        seg[ix] = max(seg[ix], MX[ix]);
        if (l != r) {
            MX[ix * 2] = max(MX[ix * 2], MX[ix]);
            MX[ix * 2 + 1] = max(MX[ix * 2 + 1], MX[ix]);
        }
        MX[ix] = -inf * 2;
    }
}

void upd(int ix, int nl, int nr, int l, int r, ll v, int f) {
    upd_lazy(ix, nl, nr);
    if (nl > r || nr < l) return;
    if (nl >= l && nr <= r) {
        if (!f) ADD[ix] += v, MX[ix] += v;
        else MX[ix] = max(MX[ix], v);
        upd_lazy(ix, nl, nr);
        return;
    }
    int m = (nl + nr) / 2;
    upd(ix * 2, nl, m, l, r, v, f);
    upd(ix * 2 + 1, m + 1, nr, l, r, v, f);
    seg[ix] = max(seg[ix * 2], seg[ix * 2 + 1]);
}

ll qry(int ix, int nl, int nr, int l, int r) {
    upd_lazy(ix, nl, nr);
    if (nl > r || nr < l) return -inf;
    if (nl >= l && nr <= r) return seg[ix];
    int m = (nl + nr) / 2;
    return max(qry(ix * 2, nl, m, l, r), qry(ix * 2 + 1, m + 1, nr, l, r));
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    vector<tuple<ll, ll, ll>> Qry;
    ll sum = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> A[i] >> S[i] >> P[i];
        sumA[i] = sumA[i - 1] + A[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> B[i] >> T[i] >> Q[i];
        sumB[i] = sumB[i - 1] + B[i];
    }
    for (int i = 1; i <= n; i++) {
        ll y = upper_bound(sumB, sumB + m + 1, S[i] - sumA[i]) - sumB - 1;
        if (y >= 0) Qry.emplace_back(i, -y, P[i]);
    }
    for (int i = 1; i <= m; i++) {
        ll x = upper_bound(sumA, sumA + n + 1, T[i] - sumB[i]) - sumA - 1;
        if (x >= 0) {
            sum += Q[i];
            if (x < n) Qry.emplace_back(x + 1, -(i - 1), -Q[i]);
        }
    }

    sort(all(Qry));
    // init
    memset(seg, 0xc1, sizeof(seg));
    memset(MX, 0xc1, sizeof(MX));
    for (int i = 0; i <= m; i++) seg[b + i] = 0;
    for (int i = b - 1; i; i--) seg[i] = max(seg[i * 2], seg[i * 2 + 1]);

    for (auto&[x, y, p] : Qry) {
        y = -y;
        upd(1, 0, b - 1, 0, y, p, 0); // add
        ll mx = qry(1, 0, b - 1, y, y);
        upd(1, 0, b - 1, y, m, mx, 1); // max
    }
    cout << sum + qry(1, 0, b - 1, m, m);
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9