Submission #641364

#	Time	Username	Problem	Language	Result	Execution time	Memory
641364		skittles1412	Food Court (JOI21_foodcourt)	C++17	100 / 100	888 ms	64060 KiB

foodcourt

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                           \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" \
         << ": ";                                          \
    dbgh(__VA_ARGS__)
#else
#define cerr   \
    if (false) \
    cerr
#define dbg(...)
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

struct Node {
    long mn, sm;

    Node operator+(const Node& n) const {
        return {min(mn, sm + n.mn), sm + n.sm};
    }

    long solve() const {
        return sm - mn;
    }

    static Node from(long x) {
        return {min(long(0), x), x};
    }

    static Node def() {
        return Node::from(0);
    }
};

struct ST {
    int n;
    vector<Node> v;

    ST(int n) : n(n), v(4 * n, Node::def()) {}

    void update(int o, int l, int r, int ind, const Node& x) {
        if (l == r) {
            v[o] = x;
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ind <= mid) {
            update(lc, l, mid, ind, x);
        } else {
            update(rc, mid + 1, r, ind, x);
        }
        v[o] = v[lc] + v[rc];
    }

    void update(int ind, const Node& x) {
        update(1, 0, n - 1, ind, x);
    }

    Node query(int o, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return v[o];
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ql <= mid) {
            if (mid < qr) {
                return query(lc, l, mid, ql, qr) +
                       query(rc, mid + 1, r, ql, qr);
            }
            return query(lc, l, mid, ql, qr);
        }
        return query(rc, mid + 1, r, ql, qr);
    }

    Node query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }
};

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    long queries[q][5];
    for (auto& [t, l, r, k, c] : queries) {
        cin >> t;
        if (t == 1) {
            cin >> l >> r >> c >> k;
        } else if (t == 2) {
            cin >> l >> r >> k;
        } else {
            cin >> l >> r;
        }
        l--;
        r--;
    }
    vector<pair<int, int>> evts[n + 1];
    for (int i = 0; i < q; i++) {
        auto& [t, l, r, _k, _c] = queries[i];
        if (t == 1 || t == 2) {
            evts[l].emplace_back(t * 2 + 0, i);
            evts[r + 1].emplace_back(t * 2 + 1, i);
        } else if (t == 3) {
            evts[l].emplace_back(-1, i);
        }
    }
    ST st(q), st2(q);
    long ans[q];
    for (int i = 0; i < n; i++) {
        dbg(i);
        for (auto& [t, j] : evts[i]) {
            if (t == -1) {
                long cleft = st.query(0, j).solve(), ind = queries[j][2],
                     cind = cleft - ind - 1;
                if (ind >= cleft) {
                    ans[j] = 0;
                    continue;
                }
                dbg(cleft, cind);
                int l = 0, r = j;
                while (l < r) {
                    int mid = (l + r + 1) / 2;
                    if (st2.query(mid, j).solve() > cind) {
                        l = mid;
                    } else {
                        r = mid - 1;
                    }
                }
                dbg(l, st.query(l, j).solve());
                ans[j] = queries[l][4];
            } else if (t & 1) {
                dbg("DEF", j);
                st.update(j, Node::def());
                st2.update(j, Node::def());
            } else if (t == 2) {
                dbg("UPD", j, queries[j][3]);
                st.update(j, Node::from(queries[j][3]));
                st2.update(j, Node::from(queries[j][3]));
            } else {
                dbg("UPD", j, -queries[j][3]);
                st.update(j, Node::from(-queries[j][3]));
            }
        }
    }
    for (int i = 0; i < q; i++) {
        if (queries[i][0] == 3) {
            cout << ans[i] << endl;
        }
    }
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin.exceptions(ios::failbit);
    solve();
}

• 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