Submission #976861

#	Time	Username	Problem	Language	Result	Execution time	Memory
976861		zwezdinv	Food Court (JOI21_foodcourt)	C++17	68 / 100	1116 ms	363984 KiB

foodcourt

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

using ll = long long;

const int N = 2.5e5;

namespace ST {
    ll mn[4 * N], s_mn[4 * N], upd[4 * N], upd_mn[4 * N];
    int cnt[4 * N];

    void apply(int node, ll x) {
        mn[node] += x;
        s_mn[node] += x;
        upd_mn[node] += x;
        upd[node] += x;
    }

    void apply_mn(int node, ll x) {
        upd_mn[node] = max(upd_mn[node], x);
        mn[node] = max(mn[node], upd_mn[node]);
    }

    void push(int node) {
        apply(node << 1, upd[node]);
        apply(node << 1 | 1, upd[node]);
        apply_mn(node << 1, upd_mn[node]);
        apply_mn(node << 1 | 1, upd_mn[node]);
        upd[node] = 0;
        upd_mn[node] = -1e17;
    }

    void pull(int node) {
        mn[node] = min(mn[node << 1], mn[node << 1 | 1]);
        cnt[node] = 0;
        if (mn[node << 1] == mn[node]) cnt[node] += cnt[node << 1];
        if (mn[node << 1 | 1] == mn[node]) cnt[node] += cnt[node << 1 | 1];
        s_mn[node] = 1e17;
        for (auto x : {mn[node << 1], s_mn[node << 1], mn[node << 1 | 1], s_mn[node << 1 | 1]}) {
            if (x != mn[node]) s_mn[node] = min(s_mn[node], x);
        }
    }

    void update(int ql, int qr, int x, int node = 1, int l = 0, int r = N - 1) {
        if (r < ql || qr < l) return;
        if (ql <= l && r <= qr) {
            // cout << 11 << ' ' << node << ' ' << l << ' ' << r << ' ' << ql << ' ' << qr << ' ' << x << ' ' << mn[node] << ' ' << s_mn[node] << ' ' << cnt[node] << endl;
            apply(node, x);
//            cout << l << ' ' << r << ' ' << mn[node] << ' ' << s_mn[node] << ' ' << cnt[node] << endl;
            return;
        }
//        cout << node << ' ' << l << ' ' << r << ' ' << mn[node] << ' ' << s_mn[node] << ' ' << cnt[node] << endl;
        push(node);
        int m = (l + r) / 2;
        update(ql, qr, x, node << 1, l, m);
        update(ql, qr, x, node << 1 | 1, m + 1, r);
        pull(node);
//        cout << l << ' ' << r << ' ' << mn[node] << ' ' << s_mn[node] << ' ' << cnt[node] << endl;
    }

    void fix(int node = 1, int l = 0, int r = N - 1) {
//        cout << l << ' ' << r << ' ' << mn[node] << ' ' << s_mn[node] << ' ' << cnt[node] << endl;
        if (mn[node] >= 0) return;
        if (s_mn[node] > 0) {
            apply_mn(node, 0);
//            cout << 11 << ' ' << l << ' ' << r << ' ' << mn[node] << ' ' << s_mn[node] << ' ' << cnt[node] << endl;
            return;
        }
        push(node);
        int m = (l + r) / 2;
        fix(node << 1, l, m);
        fix(node << 1 | 1, m + 1, r);
        pull(node);
//        cout << l << ' ' << r << ' ' << mn[node] << ' ' << s_mn[node] << ' ' << cnt[node] << endl;
    }

    ll get(int k, int node = 1, int l = 0, int r = N - 1) {
        if (l == r) return mn[node];
        push(node);
        int m = (l + r) / 2;
        if (k <= m) return get(k, node << 1, l, m);
        else return get(k, node << 1 | 1, m + 1, r);
    }

    void build(int node = 1, int l = 0, int r = N - 1) {
        if (l == r) {
            mn[node] = 0;
            cnt[node] = 1;
            s_mn[node] = 1e17;
            upd[node] = 0;
            upd_mn[node] = -1e17;
        } else {
            int m = (l + r) / 2;
            build(node << 1, l, m);
            build(node << 1 | 1, m + 1, r);
            pull(node);
        }
    }
}

const int B = 500;

vector<int> t_block[B], t_elem[N];
vector<ll> pref_block[B], pref_elem[N];
int col[N];

int main() {
    cin.tie(nullptr)->sync_with_stdio(0);

    for (int i = 0; i < B; ++i) pref_block[i] = {0};
    for (int i = 0; i < N; ++i) pref_elem[i] = {0};
    ST::build();

    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r;
            ll b;
            cin >> l >> r >> col[i] >> b;
            --l, --r;
            ST::update(l, r, b);
            for (; l <= r; l++) {
                if (l % B == 0 && l + B - 1 <= r) {
                    t_block[l / B].push_back(i);
                    pref_block[l / B].push_back(pref_block[l / B].back() + b);
                    l += B - 1;
                } else {
                    t_elem[l].push_back(i);
                    pref_elem[l].push_back(pref_elem[l].back() + b);
                }
            }
        } else if (t == 2) {
            int l, r;
            ll k;
            cin >> l >> r >> k;
            --l, --r;
            ST::update(l, r, -k);
            ST::fix();
        } else {
            int a;
            ll b;
            cin >> a >> b;
            --a;
            ll all = ST::get(a);
//            cerr << a << ' ' << all << endl;
            if (b > all) {
                cout << "0\n";
                continue;
            }
            b = all - b + 1;
//            cerr << i << ' ' << a << ' ' << b << endl;
            int L = -1, R = i;
            while (R - L > 1) {
                int M = (L + R) / 2;
                ll s_block = pref_block[a / B].back() - pref_block[a / B][upper_bound(t_block[a / B].begin(), t_block[a / B].end(), M) - t_block[a / B].begin()];
                // cerr << s_block << endl;
                ll s_elem = pref_elem[a].back() - pref_elem[a][upper_bound(t_elem[a].begin(), t_elem[a].end(), M) - t_elem[a].begin()];
                if (s_block + s_elem >= b) L = M;
                else R = M;
            }
            cout << col[R] << '\n';
        }
//        cerr << i << endl;
    }
}

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