Submission #1032427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032427		Blagoj	Food Court (JOI21_foodcourt)	C++17	100 / 100	361 ms	88748 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 3e5 + 100;

vector<pair<ll, ll>> qs[mxn], fs[mxn], xs[mxn]; 
ll l[mxn], r[mxn], c[mxn], k[mxn], a[mxn], b[mxn];

struct Node {
    ll sum = 0, suf = 0, total = 0;
} null;

struct SGT {
    vector<Node> sgt;

    SGT(int sz) {
        sgt.resize(4 * sz);
    }

    void merge(Node &k, Node k1, Node k2) {
        k.sum = k1.sum + k2.sum;
        k.suf = max(k2.suf, k1.suf + k2.sum);
    }

    void fix(int k, int l, int r, int i, ll val) {
        if (l > i || r < i) return;
        if (l == r) {
            sgt[k].sum = val;
            sgt[k].suf = max(val, 0LL);
            return;
        }
        int mid = (l + r) / 2;
        fix(k * 2, l, mid, i, val);
        fix(k * 2 + 1, mid + 1, r, i, val);
        merge(sgt[k], sgt[k * 2], sgt[k * 2 + 1]);
    }

    void update(int k, int l, int r, int i, ll val) {
        if (l > i || r < i) return;
        if (l == r) {
            sgt[k].total = val;
            return;
        }
        int mid = (l + r) / 2;
        update(k * 2, l, mid, i, val);
        update(k * 2 + 1, mid + 1, r, i, val);
        sgt[k].total = sgt[k * 2].total + sgt[k * 2 + 1].total;
    }

    Node mx(int k, int l, int r, int i, int j) {
        if (l > j || r < i) return null;
        if (i <= l && r <= j) return sgt[k];
        int mid = (l + r) / 2;
        Node ansL = mx(k * 2, l, mid, i, j), ansR = mx(k * 2 + 1, mid + 1, r, i, j);
        Node ans;
        merge(ans, ansL, ansR);
        return ans;
    }

    ll get(int k, int l, int r, int i, int j) {
        if (l > j || r < i) return 0;
        if (i <= l && r <= j) return sgt[k].total;
        int mid = (l + r) / 2;
        return get(k * 2, l, mid, i, j) + get(k * 2 + 1, mid + 1, r, i, j);
    }

    ll walk(int k, int l, int r, ll i) {
        if (l == r) return sgt[k].total > i ? l : l + 1;
        int mid = (l + r) / 2;
        if (sgt[k * 2].total > i) return walk(k * 2, l, mid, i);
        return walk(k * 2 + 1, mid + 1, r, i - sgt[k * 2].total);
    }
} sgt(mxn);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < q; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            cin >> l[i] >> r[i] >> c[i] >> k[i];
            qs[l[i]].push_back({i, k[i]});
            qs[r[i] + 1].push_back({i, 0});
            fs[l[i]].push_back({i, k[i]});
            fs[r[i] + 1].push_back({i, 0});
        }
        if (type == 2) {
            cin >> l[i] >> r[i] >> k[i];
            qs[l[i]].push_back({i, -k[i]});
            qs[r[i] + 1].push_back({i, 0});
        }
        if (type == 3) {
            cin >> a[i] >> b[i];
            xs[a[i]].push_back({i, b[i]});
        }
    }
    ll ans[q + 10];
    memset(ans, -1, sizeof(ans));
    for (int i = 1; i <= n; i++) {
        for (auto x : qs[i]) sgt.fix(1, 0, q - 1, x.first, x.second);
        for (auto x : fs[i]) sgt.update(1, 0, q - 1, x.first, x.second);
        for (auto x : xs[i]) {
            Node val = sgt.mx(1, 0, q - 1, 0, x.first);
            if (val.suf < x.second) {
                ans[x.first] = 0;
                continue; 
            }
            ll ind = sgt.get(1, 0, q - 1, 0, x.first) - val.suf + x.second;
            ans[x.first] = c[sgt.walk(1, 0, q - 1, ind - 1)]; 
        }
    }
    for (int i = 0; i < q; i++) {
        if (ans[i] != -1) cout << ans[i] << 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