Submission #1171365

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171365		patgra	Two Dishes (JOI19_dishes)	C++20	100 / 100	4844 ms	193984 KiB

dishes

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

constexpr ll inf = 2e18;
int tb;
vector<ll> t, la, lm;

void push(int v) {
    if(v >= tb) return;
    t[2 * v] = max(t[2 * v], lm[v]) + la[v];
    t[2 * v + 1] = max(t[2 * v + 1], lm[v]) + la[v];
    lm[2 * v] = max(lm[2 * v], lm[v] - la[2 * v]);
    la[2 * v] += la[v];
    lm[2 * v + 1] = max(lm[2 * v + 1], lm[v] - la[2 * v + 1]);
    la[2 * v + 1] += la[v];
    la[v] = 0, lm[v] = -inf;
}

void tAdd(int l, int r, ll x, int ml = 0, int mr = tb - 1,  int v = 1) {
    push(v);
    if(r < ml || mr < l) return;
    if(l <= ml && mr <= r) {
        t[v] += x;
        la[v] += x;
        return;
    }
    tAdd(l, r, x, ml, (ml + mr) / 2, v * 2);
    tAdd(l, r, x, (ml + mr) / 2 + 1, mr, v * 2 + 1);
    t[v] = max(t[2 * v], t[2 * v  +1]);
}
void tMax(int l, int r, ll x, int ml = 0, int mr = tb - 1,  int v = 1) {
    push(v);
    if(r < ml || mr < l) return;
    if(l <= ml && mr <= r) {
        t[v] = max(t[v], x);
        lm[v] = max(lm[v], x);
        return;
    }
    tMax(l, r, x, ml, (ml + mr) / 2, v * 2);
    tMax(l, r, x, (ml + mr) / 2 + 1, mr, v * 2 + 1);
    t[v] = max(t[2 * v], t[2 * v  +1]);
}
ll tq(int i) {
    stack<int> st;
    int ogI = i;
    i += tb;
    while(i / 2) i /= 2, st.push(i);
    while(!st.empty()) push(st.top()), st.pop();
    return t[ogI + tb];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<ll> a(n), aWhen(n), aAdd(n), b(m), bWhen(m), bAdd(m), aPrefSum(n + 1, 0), bPrefSum(m + 1, 0);
    rep(i, 0, n) cin >> a[i] >> aWhen[i] >> aAdd[i], aPrefSum[i + 1] = aPrefSum[i] + a[i];
    rep(i, 0, m) cin >> b[i] >> bWhen[i] >> bAdd[i], bPrefSum[i + 1] = bPrefSum[i] + b[i];
    vector<vector<pair<int, ll>>> aBeforeB(n);
    ll startingSum = 0;
    rep(i, 0, n) if(aWhen[i] >= aPrefSum[i + 1]) {
        if(aWhen[i] >= aPrefSum[i + 1] + bPrefSum[m]) { startingSum += aAdd[i]; DC << " SS += " << aAdd[i] << "(" << i << "a)" << eol; continue; }
        aBeforeB[i].pb({ ranges::upper_bound(bPrefSum, aWhen[i] - aPrefSum[i + 1]) - bPrefSum.begin() - 1, aAdd[i] });
    }
    rep(i, 0, m) if(bWhen[i] >= bPrefSum[i + 1]) {
        int bBeforeA = ranges::upper_bound(aPrefSum, bWhen[i] - bPrefSum[i + 1]) - aPrefSum.begin() - 1;
        startingSum += bAdd[i];
        DC << " SS += " << bAdd[i] << '(' << i << "b)" << eol;
        if(bBeforeA < n) aBeforeB[bBeforeA].pb({i, -bAdd[i]});
    }
    rep(i, 0, n) repIn2(bb, ad, aBeforeB[i]) DC << "If " << i << "a is done before " << bb << "b, then we get + " << ad << eol;
    DC << "StartingSum = " << startingSum << eol;

    tb = 1 << (32 - __builtin_clz(m + 2));
    t.resize(tb * 2, startingSum);
    la.resize(tb * 2, 0);
    lm.resize(tb * 2, -inf);

    rep(i, 0, n) {
        ranges::sort(aBeforeB[i]);
        repIn2(j, add, aBeforeB[i]) { tAdd(0, j, add); DC << "tAdd(" << 0 << ' ' << j << ' ' << add << ")" << eol; }
        repIn2(j, add, aBeforeB[i]) { DC << "tMax(" << j << ' ' << m << ' ' << tq(j) << ")" << eol; tMax(j, m, tq(j)); }
    }
    rep(i, 0, m + 1) DC << tq(i) << ' ';
    DC << eol;
    cout << tq(m) << eol;
}

• 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