Submission #1072855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072855		Double_Slash	Two Dishes (JOI19_dishes)	C++17	100 / 100	4706 ms	298964 KiB

dishes

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INF = 1e18;
int N, M, a[1000000], b[1000000], p[1000000], q[1000000];
ll s[1000000], t[1000000], psa[1000001], psb[1000001], off;
vector<int> rem[1000001];

struct Node {
    int l, r;
    ll val = 0, lazychmax = -INF, lazyadd = 0;
    Node *lc, *rc;

    Node(int l, int r) : l(l), r(r) {
        if (l < r) {
            int m = (l + r) >> 1;
            lc = new Node{l, m};
            rc = new Node{m + 1, r};
        }
    }

    void clean() {
        if (lazychmax != -INF) {
            if (l == r) val = max(val, lazychmax);
            else {
                lc->lazychmax = max(lc->lazychmax, lazychmax - lc->lazyadd);
                rc->lazychmax = max(rc->lazychmax, lazychmax - rc->lazyadd);
            }
            lazychmax = -INF;
        }
        if (lazyadd) {
            if (l == r) val += lazyadd;
            else {
                lc->lazyadd += lazyadd;
                rc->lazyadd += lazyadd;
            }
            lazyadd = 0;
        }
    }

    void add(int ul, int ur, ll v) {
        clean();
        if (ul > r or ur < l) return;
        if (l >= ul and r <= ur) lazyadd += v;
        else lc->add(ul, ur, v), rc->add(ul, ur, v);
    }

    ll chmax(int i) {
        clean();
        if (l == r) return val;
        int m = (l + r) >> 1;
        if (i <= m) {
            rc->clean();
            return rc->lazychmax = lc->chmax(i);
        } else return rc->chmax(i);
    }
};

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        cin >> a[i] >> s[i] >> p[i];
        psa[i + 1] = psa[i] + a[i];
    }
    for (int i = 0; i < M; ++i) {
        cin >> b[i] >> t[i] >> q[i];
        psb[i + 1] = psb[i] + b[i];
        auto it = upper_bound(psa, psa + N + 1, t[i] - psb[i + 1]);
        if (it - psa > N) off += q[i];
        else if (it != psa) rem[it - psa].emplace_back(i);
    }
    Node root{0, M};
    for (int i = 1; i <= N; ++i) {
        auto it = upper_bound(psb, psb + M + 1, s[i - 1] - psa[i]);
        if (it != psb) root.add(0, it - psb - 1, p[i - 1]);
        for (int j: rem[i]) root.add(j + 1, M, q[j]);
        for (int j: rem[i]) root.chmax(j);
        if (it != psb) root.chmax(it - psb - 1);
    }
    cout << root.chmax(M) + off;
}

• 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