Submission #1007343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007343		LOLOLO	Food Court (JOI21_foodcourt)	C++17	100 / 100	521 ms	110988 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 3e5 + 20;

struct seg{
    vector <ll> sum, mi;
    seg(int n) {
        sum.assign(n * 4 + 100, 0);
        mi.assign(n * 4 + 100, 0);
    }

    void upd(int i, int l, int r, int p, ll v) {
        if (l > p || r < p)
            return;

        if (l == r) {
            sum[i] += v;
            mi[i] = min((ll)0, sum[i]);
            return; 
        }

        int m = (l + r) / 2;
        upd(i * 2, l, m, p, v);
        upd(i * 2 + 1, m + 1, r, p, v);
        sum[i] = sum[i * 2] + sum[i * 2 + 1];
        mi[i] = min(mi[i * 2], sum[i * 2] + mi[i * 2 + 1]);
    }

    pair <ll, ll> get(int i, int l, int r, int u) {
        if (l > u)
            return {0, 0};

        if (r <= u)
            return {sum[i], mi[i]};

        int m = (l + r) / 2;
        pair <ll, ll> A = get(i * 2, l, m, u), B = get(i * 2 + 1, m + 1, r, u);
        return {A.f + B.f, min(A.s, B.s + A.f)};
    }
};

struct fen{
    vector <ll> f;
    int N;
    fen(int n) {
        N = n;
        f.assign(n + 1, 0);
    }

    void upd(int i, int x) {
        for (; i <= N; i += i & (-i))
            f[i] += x;
    }

    ll get(int i) {
        ll s = 0;
        for (; i; i -= i & (-i))
            s += f[i];

        return s;
    }
};

struct ST{
    vector <pair <ll, ll>> st;
    vector <ll> laz;

    void build(int i, int l, int r) {
        if (l == r) {
            st[i] = {0, l};
            return;
        }

        int m = (l + r) / 2;
        build(i * 2, l, m);
        build(i * 2 + 1, m + 1, r);
        st[i] = min(st[i * 2], st[i * 2 + 1]);
    }

    ST(int n) {
        st.assign(n * 4 + 10, {0, 0});
        laz.assign(n * 4 + 10, 0);
        build(1, 1, n);
    }

    void push(int i) {
        ll t = laz[i];
        laz[i * 2] += t;
        laz[i * 2 + 1] += t;
        st[i * 2].f += t;
        st[i * 2 + 1].f += t;
        laz[i] = 0;
    }

    void upd(int i, int l, int r, int u, int v, ll c) {
        if (l > v || r < u)
            return;

        if (l >= u && r <= v) {
            laz[i] += c;
            st[i].f += c;
            return;
        }

        push(i);
        int m = (l + r) / 2;
        upd(i * 2, l, m, u, v, c);
        upd(i * 2 + 1, m + 1, r, u, v, c);
        st[i] = min(st[i * 2], st[i * 2 + 1]);
    }

    pair <ll, ll> get() {
        return st[1];
    }
};

ll ans[N];
bool is[N];

vector < pair <ll, ll>> event[N], add[N], ask[N], save[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    vector < vector <ll>> need;
    int n, m, q;
    cin >> n >> m >> q;

    fen bit(q);
    seg seg(q);
    ST st(n);

    for (int i = 1; i <= q; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            ll l, r, c, k;
            cin >> l >> r >> c >> k;
            need.pb({l, r, c, k});
            add[l].pb({i, k});
            add[r + 1].pb({i, -k});
            event[l].pb({i, k});
            event[r + 1].pb({i, -k});
        }

        if (t == 2) {
            ll l, r, k;
            cin >> l >> r >> k;
            event[l].pb({i, -k});
            event[r + 1].pb({i, k});   
        }

        if (t == 3) {
            ll a, b;
            cin >> a >> b;
            ask[a].pb({i, b});
            is[i] = 1;
        }
    }

    for (int i = 1; i <= n; i++) {
        for (auto x : event[i]) {
            seg.upd(1, 1, q, x.f, x.s);
        }

        for (auto x : add[i]) {
            bit.upd(x.f, x.s);
        }

        for (auto x : ask[i]) {
            pair <ll, ll> tt = seg.get(1, 1, q, x.f);
            ll num = tt.f - tt.s;
            if (num >= x.s) {
                save[i].pb({bit.get(x.f) - (num - x.s), x.f});
            }
        }

        sort(all(save[i]), greater <pair <ll, ll>> ());
        if (sz(save[i])) {
            st.upd(1, 1, n, i, i, save[i].back().f);
        } else {
            st.upd(1, 1, n, i, i, 1e16);
        }
    }

    for (auto x : need) {
        st.upd(1, 1, n, x[0], x[1], -x[3]);
        while (1) {
            pair <ll, ll> tt = st.get();
            if (tt.f <= 0) {
                int i = tt.s;
                ans[save[i].back().s] = x[2];
                ll pr = save[i].back().f;
                save[i].pop_back();
                if (sz(save[i])) {
                    st.upd(1, 1, n, i, i, save[i].back().f - pr);
                } else {
                    st.upd(1, 1, n, i, i, 1e16 - pr);
                }
            } else {
                break;
            }
        }
    }

    for (int i = 1; i <= q; i++) {
        if (is[i]) {
            cout << ans[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