Submission #1215394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215394		adaawf	Food Court (JOI21_foodcourt)	C++20	100 / 100	392 ms	72924 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct FOOD {
    int w, l, r, c, k;
} a[250005];
vector<pair<int, int>> g[250005], gg[250005], ga[250005];
struct COURT {
    int mi, c;
} t[1000015];
int lazy[1000015], res[250005];
void push(int v) {
    lazy[v << 1] += lazy[v];
    lazy[v << 1 | 1] += lazy[v];
    t[v << 1].mi += lazy[v];
    t[v << 1].c += lazy[v];
    t[v << 1 | 1].mi += lazy[v];
    t[v << 1 | 1].c += lazy[v];
    lazy[v] = 0;
}
COURT Merge(COURT aa, COURT bb) {
    COURT res;
    res.mi = min(aa.mi, bb.mi);
    res.c = bb.c;
    return res;
}
void update(int v, int tl, int tr, int l, int r, int x) {
    if (l > r) return;
    if (tl == l && tr == r) {
        t[v].mi += x;
        t[v].c += x;
        lazy[v] += x;
        return;
    }
    push(v);
    int mid = (tl + tr) >> 1;
    update(v << 1, tl, mid, l, min(r, mid), x);
    update(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r, x);
    t[v] = Merge(t[v << 1], t[v << 1 | 1]);
}
COURT sum(int v, int tl, int tr, int l, int r) {
    if (l > r) return {1000000000000000000, 0};
    if (tl == l && tr == r) {
        return t[v];
    }
    push(v);
    int mid = (tl + tr) >> 1;
    return Merge(sum(v << 1, tl, mid, l, min(r, mid)), sum(v << 1 | 1, mid + 1, tr, max(l, mid + 1), r));
}
int sum2(int v, int tl, int tr, int x) {
    if (tl == tr) {
        return tl;
    }
    push(v);
    int mid = (tl + tr) >> 1;
    if (t[v << 1].c >= x) return sum2(v << 1, tl, mid, x);
    return sum2(v << 1 | 1, mid + 1, tr, x);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= q; i++) {
        int w, l, r, c, k;
        cin >> w;
        if (w == 1) {
            cin >> l >> r >> c >> k;
            g[l].push_back({k, i});
            g[r + 1].push_back({-k, i});
            ga[l].push_back({k, i});
            ga[r + 1].push_back({-k, i});
        }
        else if (w == 2) {
            cin >> l >> r >> k;
            g[l].push_back({-k, i});
            g[r + 1].push_back({k, i});
        }
        else {
            cin >> l >> r;
            gg[l].push_back({r, i});
        }
        a[i] = {w, l, r, c, k};
    }
    for (int i = 1; i <= n; i++) {
        for (auto w : g[i]) {
            update(1, 0, q, w.second, q, w.first);
        }
        for (auto w : gg[i]) {
            COURT h = sum(1, 0, q, 0, w.second);
            int c = sum(1, 0, q, w.second, w.second).mi - h.mi;
            res[w.second] = c;
        }
    }
    for (int i = 1; i <= (q + 1) * 4; i++) {
        t[i] = {0, 0};
        lazy[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (auto w : ga[i]) {
            update(1, 0, q, w.second, q, w.first);
        }
        for (auto w : gg[i]) {
            if (res[w.second] < w.first) res[w.second] = 0;
            else {
                COURT h = sum(1, 0, q, w.second, w.second);
                int k = h.mi - (res[w.second] - w.first);
                int l = sum2(1, 0, q, k);
                res[w.second] = a[l].c;
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        if (a[i].w == 3) {
            cout << res[i] << '\n';
        }
    }
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11