Submission #933765

#	Time	Username	Problem	Language	Result	Execution time	Memory
933765		Pannda	Food Court (JOI21_foodcourt)	C++17	100 / 100	528 ms	74820 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct SegmentTree {
    int n;
    vector<long long> a, b;

    SegmentTree(int n) : n(n), a(4 * n, 0), b(4 * n, 0) {}

    void apply(int idx, long long x, long long y) {
        b[idx] = max(b[idx] + x, y);
        a[idx] = a[idx] + x;
    }

    void down(int idx) {
        apply(2 * idx + 1, a[idx], b[idx]);
        apply(2 * idx + 2, a[idx], b[idx]);
        a[idx] = b[idx] = 0;
    }

    void add(int ql, int qr, long long x, long long y) {
        auto dfs = [&](auto self, int idx, int l, int r) {
            if (r <= ql || qr <= l) return;
            if (ql <= l && r <= qr) return apply(idx, x, y);
            down(idx);
            int m = (l + r) >> 1;
            self(self, 2 * idx + 1, l, m);
            self(self, 2 * idx + 2, m, r);
        };
        dfs(dfs, 0, 0, n);
    }

    long long get(int pos) {
        int idx = 0, l = 0, r = n;
        while (l + 1 < r) {
            down(idx);
            int m = (l + r) >> 1;
            if (pos < m) {
                idx = 2 * idx + 1;
                r = m;
            } else {
                idx = 2 * idx + 2;
                l = m;
            }
        }
        return max(a[idx], b[idx]);
    }
};

struct Fenwick {
    int n;
    vector<long long> bit;

    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int i, long long delta) {
        for (i++; i <= n; i += i & -i) {
            bit[i] += delta;
        }
    }

    void add(int ql, int qr, long long delta) {
        add(ql, +delta);
        add(qr, -delta);
    }

    long long get(int i) {
        long long res = 0;
        for (i++; i > 0; i -= i & -i) {
            res += bit[i];
        }
        return res;
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    vector<int> type(q), l(q), r(q), c(q), k(q), a(q), b(q);
    for (int i = 0; i < q; i++) {
        cin >> type[i];
        if (type[i] == 1) {
            cin >> l[i] >> r[i] >> c[i] >> k[i];
            l[i]--;
        }
        if (type[i] == 2) {
            cin >> l[i] >> r[i] >> k[i];
            l[i]--;
        }
        if (type[i] == 3) {
            cin >> a[i] >> b[i];
            a[i]--;
            b[i]--;
        }
    }

    SegmentTree seg(n);
    Fenwick fen(n);
    vector<vector<int>> inbox(q + 1);

    for (int i = 0; i < q; i++) {
        if (type[i] == 1) {
            seg.add(l[i], r[i], k[i], 0);
            fen.add(l[i], r[i], k[i]);
        }
        if (type[i] == 2) {
            seg.add(l[i], r[i], -k[i], 0);
        }
        if (type[i] == 3) {
            long long seg_get = seg.get(a[i]);
            long long fen_get = fen.get(a[i]);
            b[i] = fen_get - seg_get + b[i];
            l[i] = 0, r[i] = q - 1;
            inbox[(l[i] + r[i]) >> 1].push_back(i);
        }
    }

    const int LOG = 18;
    for (int ite = 0; ite < LOG; ite++) {
        Fenwick fen(n);
        vector<vector<int>> new_inbox(q + 1);
        for (int m = 0; m < q; m++) {
            if (type[m] == 1) {
                fen.add(l[m], r[m], k[m]);
            }
            for (int i : inbox[m]) {
                if (b[i] < fen.get(a[i])) {
                    r[i] = m;
                } else {
                    l[i] = m + 1;
                }
                new_inbox[(l[i] + r[i]) >> 1].push_back(i);
            }
        }
        inbox = new_inbox;
    }

    for (int i = 0; i < q; i++) {
        if (type[i] == 3) {
            if (l[i] > i) {
                cout << 0 << '\n';
            } else {
                cout << c[l[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