제출 #1332294

#제출 시각아이디문제언어결과실행 시간메모리
1332294MisterReaperTwo Dishes (JOI19_dishes)C++20
100 / 100
2100 ms158712 KiB
#include <bits/stdc++.h>

using i64 = long long;

#ifdef LOCAL
    #include "debug.h"
#else
    #define debug(...) void(23)
#endif

template<typename T>
bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

constexpr i64 inf = i64(1E18);

#define def int mid = (l + r) >> 1, lv = v + 1, rv = v + ((mid - l + 1) << 1);
struct segtree {
    struct node {
        i64 mx = -inf;
        i64 lz = 0;
        void modify(i64 x) {
            mx += x;
            lz += x;
        }
    };
    node unite(const node& lhs, const node& rhs) {
        node res;
        res.mx = std::max(lhs.mx, rhs.mx);
        return res;
    }
    int n;
    std::vector<node> tree;
    segtree(int n_) : n(n_), tree(n << 1) {}
    void push(int v, int l, int r) {
        def;
        if (tree[v].lz) {
            tree[lv].modify(tree[v].lz);
            tree[rv].modify(tree[v].lz);
            tree[v].lz = 0;
        }
    }
    void modify(int v, int l, int r, int ql, int qr, i64 x) {
        if (ql == l && r == qr) {
            tree[v].modify(x);
            return;
        }
        def;
        push(v, l, r);
        if (qr <= mid) {
            modify(lv, l, mid, ql, qr, x);
        } else if (mid + 1 <= ql) {
            modify(rv, mid + 1, r, ql, qr, x);
        } else {
            modify(lv, l, mid, ql, mid, x);
            modify(rv, mid + 1, r, mid + 1, qr, x);
        }
        tree[v] = unite(tree[lv], tree[rv]);
    }
    void modify(int l, int r, i64 x) {
        modify(0, 0, n - 1, l, r, x);
    }
    void set(int v, int l, int r, int p, i64 x) {
        if (l == r) {
            tree[v] = {x};
            return;
        }
        def;
        push(v, l, r);
        if (p <= mid) {
            set(lv, l, mid, p, x);
        } else {
            set(rv, mid + 1, r, p, x);
        }
        tree[v] = unite(tree[lv], tree[rv]);
    }
    void set(int p, i64 x) {
        set(0, 0, n - 1, p, x);
    }
    i64 get(int v, int l, int r, int ql, int qr) {
        if (ql == l && r == qr) {
            return tree[v].mx;
        }
        def;
        push(v, l, r);
        if (qr <= mid) {
            return get(lv, l, mid, ql, qr);
        } else if (mid + 1 <= ql) {
            return get(rv, mid + 1, r, ql, qr);
        } else {
            return std::max(get(lv, l, mid, ql, mid),
                            get(rv, mid + 1, r, mid + 1, qr));
        }
    }
    i64 get(int l, int r) {
        return get(0, 0, n - 1, l, r);
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N, M;
    std::cin >> N >> M;

    std::vector<std::array<i64, 3>> A(N), B(M);
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i][0] >> A[i][1] >> A[i][2];
    }
    for (int i = 0; i < M; ++i) {
        std::cin >> B[i][0] >> B[i][1] >> B[i][2];
    }

    std::vector<i64> pa(N + 1), pb(M + 1);
    for (int i = 0; i < N; ++i) {
        pa[i + 1] = pa[i] + A[i][0];
    }
    for (int i = 0; i < M; ++i) {
        pb[i + 1] = pb[i] + B[i][0];
    }

    i64 ans = 0;

    segtree seg(M + 1);
    std::vector<std::vector<std::pair<int, int>>> upd(N);

    for (int i = 0; i < N; ++i) {
        if (pa[i + 1] <= A[i][1]) {
            int lo = 0, hi = M;
            while (lo < hi) {
                int mid = (lo + hi + 1) >> 1;
                if (pa[i + 1] + pb[mid] <= A[i][1]) {
                    lo = mid;
                } else {
                    hi = mid - 1;
                }
            }
            ans += A[i][2];
            debug(i, lo);
            if (lo != M) {
                upd[i].emplace_back(lo + 1, -A[i][2]);
            }
        }
    }

    for (int i = 0; i < M; ++i) {
        if (pb[i + 1] <= B[i][1]) {
            int lo = 0, hi = N;
            while (lo < hi) {
                int mid = (lo + hi + 1) >> 1;
                if (pa[mid] + pb[i + 1] <= B[i][1]) {
                    lo = mid;
                } else {
                    hi = mid - 1;
                }
            }
            debug(lo, i);
            if (lo == N) {
                ans += B[i][2];
            } else {
                upd[lo].emplace_back(i + 1, B[i][2]);
            }
        }
    }

    seg.set(0, 0);

    for (int i = 0; i < N; ++i) {
        std::sort(upd[i].rbegin(), upd[i].rend());
        for (int j = 0; j < int(upd[i].size()); ++j) {
            if (j == 0 || upd[i][j].first != upd[i][j - 1].first) {
                seg.set(upd[i][j].first, seg.get(0, upd[i][j].first));
            }
            seg.modify(upd[i][j].first, M, upd[i][j].second);
        }
    }

    debug(ans);

    ans += seg.get(0, M);

    std::cout << ans << '\n';

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...