Submission #480376

#	Time	Username	Problem	Language	Result	Execution time	Memory
480376		fishy15	Food Court (JOI21_foodcourt)	C++17	0 / 100	1096 ms	137864 KiB

foodcourt

#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>

#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007

#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f

// change if necessary
#define MAXN 250010

using namespace std;

template<typename T>
T &ckmin(T &a, T b) {
    return a = min(a, b);
}

struct BIT {
    int n;
    vector<ll> bit;

    BIT(int n) : n(n), bit(n) {}

    void upd(int x, ll q) {
        x++;
        while (x <= n) {
            bit[x - 1] += q;
            x += x & -x;
        }
    }

    ll qry(int x) {
        ll res = 0;
        while (x > 0) {
            res += bit[x - 1];
            x -= x & -x;
        }
        return res;
    }

    int bsearch(ll r) {
        int cur = 0;
        ll sum = 0;
        for (int i = (1 << 20); i > 0; i /= 2) {
            if (cur + i <= n && sum + bit[cur + i - 1] <= r) {
                cur += i;
                sum += bit[cur - 1];
            }
        }
        return cur;
    }
};

BIT tot_add(0);

struct segtree {
    int n;
    vector<ll> st;
    vector<ll> lazy;

    segtree(int n) : n(n), st(4 * n), lazy(4 * n) {}

    void push(int v, int l, int r) {
        if (l + 1 != r) {
            lazy[2 * v] += lazy[v];
            lazy[2 * v + 1] += lazy[v];
            ckmin(lazy[2 * v], st[2 * v]);
            ckmin(lazy[2 * v + 1], st[2 * v + 1]);
        }

        st[v] -= lazy[v];
        lazy[v] = 0;
    }

    void upd(int x, int y, ll q) { upd(1, 0, n, x, y, q); }
    void upd(int v, int l, int r, int x, int y, ll q) {
        push(v, l, r);
        ckmin(q, st[v]);
        if (r <= x || l >= y) return;
        if (x <= l && r <= y) {
            lazy[v] += q;
            push(v, l, r);
        } else {
            int m = (l + r) / 2;
            upd(2 * v, l, m, x, y, q);
            upd(2 * v + 1, m, r, x, y, q);
            st[v] = max(st[2 * v], st[2 * v + 1]);
        }
    }

    ll qry(int a, ll b) { return qry(1, 0, n, a, b); }
    ll qry(int v, int l, int r, int a, ll b) {
        push(v, l, r);
        if (l + 1 == r) {
            if (b >= st[v]) {
                return -1;
            } else {
                return tot_add.qry(a + 1) - st[v] + b;
            }
        } else {
            int m = (l + r) / 2;
            if (a < m) {
                return qry(2 * v, l, m, a, b);
            } else {
                return qry(2 * v + 1, m, r, a, b);
            }
        }
    }
};

int n, m, q;
array<ll, 5> qry[MAXN];
vector<pair<ll, int>> in_q;
vector<int> add[MAXN]; // elements to add to the queue
vector<int> rem[MAXN]; // elements to remove from the queue
vector<pair<ll, int>> to_ans[MAXN];
vector<ll> ans;

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

    cin >> n >> m >> q;
    for (int i = 0; i < q; i++) {
        qry[i] = {0, 0, 0, 0, 0};
        cin >> qry[i][0];
        switch (qry[i][0]) {
            case 1: 
                cin >> qry[i][1] >> qry[i][2] >> qry[i][3] >> qry[i][4];
                break;
            case 2:
                cin >> qry[i][1] >> qry[i][2] >> qry[i][3];
                break;
            case 3:
                cin >> qry[i][1] >> qry[i][2];
                break;
        }
    }

    segtree st(n);
    tot_add = BIT(n);

    for (int i = 0; i < q; i++) {
        auto qq = qry[i];
        if (qq[0] == 1) {
            auto [t, l, r, c, k] = qq;
            l--;
            add[l].push_back(in_q.size());
            rem[r].push_back(in_q.size());
            in_q.push_back({k, c});
            st.upd(l, r, -k);
            tot_add.upd(l, k);
            tot_add.upd(r, -k);
        } else if (qq[0] == 2) {
            auto [t, l, r, k, _] = qq;
            l--;
            st.upd(l, r, k);
        } else {
            auto [t, a, b, _, __] = qq;
            a--; b--;
            int p_idx = st.qry(a, b);
            to_ans[a].push_back({p_idx, ans.size()});
            ans.emplace_back();
        }

        for (int i = 0; i < n; i++) {
            cout << tot_add.qry(i + 1) << ' ';
        }
        cout << '\n';
    }

    int sz = in_q.size();
    BIT bit(sz);
    for (int i = 0; i < n; i++) {
        for (int x : add[i]) {
            bit.upd(x, in_q[x].first);
        }

        for (int x : rem[i]) {
            bit.upd(x, -in_q[x].first);
        }

        for (auto [loc, idx] : to_ans[i]) {
            if (loc == -1) {
                ans[idx] = 0;
            } else {
                int pos = bit.bsearch(loc);
                ans[idx] = in_q[pos].second;
            }
        }
    }

    for (int x : ans) {
        cout << x << '\n';
    }

    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