Submission #1077212

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077212		Double_Slash	Food Court (JOI21_foodcourt)	C++17	100 / 100	528 ms	53196 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

struct Val {
    ll sum = 0, pos = 0, pmin = 0, pmini;

    void operator=(ll x) {
        sum = x;
        pmin = min(0ll, x);
        pos = max(0ll, x);
    }

    Val operator+(const Val &o) const {
        Val ret{sum + o.sum, pos + o.pos};
        tie(ret.pmin, ret.pmini) = min(pll{pmin, pmini}, pll{sum + o.pmin, o.pmini});
        return ret;
    }
};

struct St {
    int n;
    vector<Val> st;

    St(int n) : n(n), st(n << 1) {
        for (int i = 0; i < n; ++i) st[i + n].pmini = i;
        for (int i = n; i--;) st[i] = st[i << 1] + st[i << 1 | 1];
    }

    void update(int i, ll v) {
        for (st[i += n] = v; i >>= 1;) st[i] = st[i << 1] + st[i << 1 | 1];
    }

    Val query(int l, int r) {
        Val lagg{0, 0, l}, ragg{0, 0, r - 1};
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) lagg = lagg + st[l++];
            if (r & 1) ragg = st[--r] + ragg;
        }
        return lagg + ragg;
    }
};

int n, m, q, c[250000];
vector<pint> add[250001];
vector<int> rem[250001];
vector<pair<int, ll>> services[250001];

int main() {
    cin >> n >> m >> q;
    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r, k;
            cin >> l >> r >> c[i] >> k;
            add[l].emplace_back(i, k);
            rem[r].emplace_back(i);
        } else if (t == 2) {
            int l, r, k;
            cin >> l >> r >> k;
            add[l].emplace_back(i, -k);
            rem[r].emplace_back(i);
        } else {
            ll a, b;
            cin >> a >> b;
            services[a].emplace_back(i, b);
        }
    }
    St st{q};
    vector<pint> ans;
    for (int i = 1; i <= n; ++i) {
        for (auto [j, k]: add[i]) {
            st.update(j, k);
        }
        for (auto [j, b]: services[i]) {
            int l = 0;
            auto v = st.query(l, j);
            if (v.pmin < 0) v = st.query(l = v.pmini + 1, j);
            if (v.sum < b) ans.emplace_back(j, 0);
            else {
                b -= v.sum - v.pos;
                int r = l;
                for (int k = 18; k--;) {
                    if (r + (1 << k) >= j) continue;
                    auto v2 = st.query(l, r + (1 << k));
                    if (v2.pos < b) r += 1 << k;
                }
                ans.emplace_back(j, c[r]);
            }
        }
        for (int j: rem[i]) {
            st.update(j, 0);
        }
    }
    sort(ans.begin(), ans.end());
    for (auto [i, a]: ans) cout << a << endl;
}

• 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