Submission #551440

#	Time	Username	Problem	Language	Result	Execution time	Memory
551440		jesus_coconut	Food Court (JOI21_foodcourt)	C++17	0 / 100	231 ms	29576 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

int const N = 1 << 18;

struct LazySegTree {
    struct Node {
        int his = 0;
        int cur = 0;

        friend Node operator*(Node ret, int val) {
            ret.cur += val;
            ret.his = min(ret.his, ret.cur);
            return ret;
        }

        friend Node operator+(Node a, Node b) {
            Node ret;
            ret.cur = a.cur + b.cur;
            ret.his = min(a.his, a.cur + b.his);
            return ret;
        }
    };

    array<Node, 2 * N> seg;

    void propagate(int ver, int lx, int rx) {
        if (rx - lx == 1) return;
        seg[2 * ver + 1] = seg[2 * ver + 1] + seg[ver];
        seg[2 * ver + 2] = seg[2 * ver + 2] + seg[ver];
        seg[ver] = {0, 0};
    }

    void add(int l, int r, int val, int ver, int lx, int rx) {
        propagate(ver, lx, rx);
        if (rx <= l || r <= lx) return;
        if (l <= lx && rx <= r) {
            seg[ver] = seg[ver] * val;
            return;
        }
        int mx = (lx + rx) / 2;
        add(l, r, val, 2 * ver + 1, lx, mx);
        add(l, r, val, 2 * ver + 2, mx, rx);
    }

    int query(int p, int ver, int lx, int rx) {
        propagate(ver, lx, rx);
        if (rx - lx == 1) return seg[ver].his;
        int mx = (rx + lx) / 2;
        if (p < mx) return query(p, 2 * ver + 1, lx, mx);
        else return query(p, 2 * ver + 2, mx, rx);
    }
};

LazySegTree st1;

struct SegTree {
    struct Node{
        int cur = 0;
        int lazy = 0;

        friend Node operator*(Node ret, int val) {
            ret.cur += val;
            ret.lazy += val;
            return ret;
        }
        friend Node operator+(Node a, Node b) {
            Node ret;
            ret.cur = min(a.cur, b.cur);
            return ret;
        }
    };
    array<Node, 2 * N> seg;

    void propagate(int ver, int lx, int rx) {
        if (rx - lx == 1) return;
        seg[2 * ver + 1] = seg[2 * ver + 1] * seg[ver].lazy;
        seg[2 * ver + 2] = seg[2 * ver + 2] * seg[ver].lazy;
        seg[ver].lazy = 0;
    }

    void pull(int ver) {
        seg[ver] = seg[2 * ver + 1] + seg[2 * ver + 2];
    }

    void upd(int l, int r, int val, int ver, int lx, int rx) {
        propagate(ver, lx, rx);
        if (rx <= l || r <= lx) return;
        if (l <= lx && rx <= r) {
            seg[ver] = seg[ver] * val;
            return;
        }
        int mx = (lx + rx) / 2;
        upd(l, r, val, 2 * ver + 1, lx, mx);
        upd(l, r, val, 2 * ver + 2, mx, rx);
        pull(ver);
    }

    int query(int l, int r, int ver, int lx, int rx) {
        propagate(ver, lx, rx);
        if (rx <= l || r <= lx) return INT_MAX;
        if (l <= lx && rx <= r) {
            return seg[ver].cur;
        }
        int mx = (rx + lx) / 2;
        int t1 = query(l, r, 2 * ver + 1, lx, mx);
        int t2 = query(l, r, 2 * ver + 2, mx, rx);
        return min(t1, t2);
    }
};

SegTree st;

struct Item {
    int t, l, r, c, k, a, b, bio = 1, time = 0;
    Item() {
        t = l = r = c = k = a = b = -1;
    }
};

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<Item> queries(q);
    vector<vector<int>> events(n + 10);
    int idx = 0;
    int tim = 0;
    for (auto &[t, l, r, c, k, a, b, bio, time] : queries) {
        cin >> t;
        if (t == 1) {
            cin >> l >> r >> c >> k;
            --l;
            events[l].push_back(idx);
            events[r].push_back(idx);
            st1.add(l, r, k, 0, 0, N);
        } else if (t == 2) {
            cin >> l >> r >> k;
            k = -k;
            --l;
            events[l].push_back(idx);
            events[r].push_back(idx);
            st1.add(l, r, k, 0, 0, N);
        } else {
            cin >> a >> b;
            --a;
            b += st1.query(a, 0, 0, N);
            time = tim++;
            events[a].push_back(idx);
        }
        ++idx;
    }
    vector<int> ans(tim);
    set<int> s;
    for (auto const &vec : events) {
        for (auto i : vec) {
            if (queries[i].t != 3) {
                st.upd(i, N, queries[i].k * queries[i].bio, 0, 0, N);
                if (queries[i].k > 0) {
                    if (queries[i].bio == 1) s.insert(i);
                    else s.erase(i);
                }
                queries[i].bio *= -1;
            } else {
                if (s.empty() || st.query(i, i + 1, 0, 0, N) < queries[i].b) {
                    ans[queries[i].time] = 0;
                    continue;
                }
                if (st.query(i, i + 1, 0, 0, N) == queries[i].b) {
                    auto it = s.lower_bound(i);
                    assert(it != s.begin());
                    --it;
                    ans[queries[i].time] = queries[*it].c;
                    continue;
                }
                int lo = 0, hi = i;
                while (lo < hi) {
                    int mid = (lo + hi) / 2;
                    int x = st.query(mid, i, 0, 0, N);
                    //cerr << x << '\n';
                    if (x <= queries[i].b) {
                        lo = mid + 1;
                    } else hi = mid;
                }
                auto it = s.lower_bound(lo);
                if (it == s.begin()) {
                    ans[queries[i].time] = queries[*it].c;
                } else {
                    if (st.query(*prev(it), *it, 0, 0, N) == queries[i].b) {
                        ans[queries[i].time] = queries[*prev(it)].c;
                    } else {
                        ans[queries[i].time] = queries[lo].c;
                    }
                }
            }
        }
    }
    for (auto a : ans) cout << a << '\n';
}

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

    solve();

    return 0;
}

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