Submission #1238656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238656		hamedddddp	Food Court (JOI21_foodcourt)	C++17	100 / 100	442 ms	84560 KiB

foodcourt

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin(), v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 2e5 + 5e4 + 5;
const int LOG = 20;

struct Info {
    int mn, ind, lazy;
};

struct SegmentTree {
    vector<Info> T;

    SegmentTree(int n) {
        T.resize(4 * n);
    }

    void push(int rt, int l, int r) {
        if (!T[rt].lazy) return;
        int u = T[rt].lazy;
        T[rt].lazy = 0;
        T[rt].mn += u;
        if (l == r) return;
        T[rt * 2].lazy += u;
        T[rt * 2 + 1].lazy += u;
    }

    Info merge(Info a, Info b) {
        if (a.ind == -1) return b;
        if (b.ind == -1) return a;
        Info res;
        res.lazy = 0;
        res.ind = (a.mn <= b.mn ? a.ind : b.ind);
        res.mn = min(a.mn, b.mn);
        return res;
    }

    void build(int rt, int l, int r) {
        if (l == r) {
            T[rt].ind = l;
            T[rt].lazy = 0;
            T[rt].mn = 0;
            return;
        }
        int mid = (l + r) / 2;
        build(rt * 2, l, mid);
        build(rt * 2 + 1, mid + 1, r);
        T[rt] = merge(T[rt * 2], T[rt * 2 + 1]);
    }

    void update(int rt, int l, int r, int gl, int gr, int val) {
        push(rt, l, r);
        if (r < gl || l > gr) return;
        if (l >= gl && r <= gr) {
            T[rt].lazy += val;
            push(rt, l, r);
            return;
        }
        int mid = (l + r) / 2;
        update(rt * 2, l, mid, gl, gr, val);
        update(rt * 2 + 1, mid + 1, r, gl, gr, val);
        T[rt] = merge(T[rt * 2], T[rt * 2 + 1]);
    }

    Info query(int rt, int l, int r, int gl, int gr) {
        push(rt, l, r);
        if (r < gl || l > gr) return {LLONG_MAX, -1, 0};
        if (l >= gl && r <= gr) return T[rt];
        int mid = (l + r) / 2;
        return merge(query(rt * 2, l, mid, gl, gr), query(rt * 2 + 1, mid + 1, r, gl, gr));
    }
};

struct FenwickTree {
    vector<vector<int>> fw;

    FenwickTree(int n) {
        fw.resize(n, vector<int>(2, 0));  // Create a 2D Fenwick tree array
    }

    void add(int ind, int val, int t) {
        for (; ind < N; ind += ind & -ind) fw[ind][t] += val;
    }

    int get(int ind, int t, int res = 0) {
        for (; ind; ind -= ind & -ind) res += fw[ind][t];
        return res;
    }

    int bs(int k, int res = 0, int p = 0) {
        for (int bit = LOG - 1; bit >= 0; bit--) {
            if (p + (1 << bit) >= N) continue;
            if (fw[p + (1 << bit)][0] < k) {
                k -= fw[p + (1 << bit)][0];
                p += (1 << bit);
            }
        }
        return p + 1;
    }
};

void solve() {
    int n, m, q;
    cin >> n >> m >> q;

    SegmentTree segTree(q);
    segTree.build(1, 0, q);

    FenwickTree fenwickTree(N);

    vector<vector<int>> Open(N), Close(N), Sor(N);
    vector<vector<int>> op(q + 1, vector<int>(4, -1));
    int ptr = 0;

    for (int i = 1; i <= q; i++) {
        int d;
        cin >> d;
        if (d == 1) {
            int l, r, k, id;
            cin >> l >> r >> id >> k;
            op[i] = {l, r, k, id};
            Open[l].push_back(i);
            Close[r + 1].push_back(i);
        } else if (d == 2) {
            int l, r, k;
            cin >> l >> r >> k;
            op[i] = {l, r, k, -1};
            Open[l].push_back(i);
            Close[r + 1].push_back(i);
        } else {
            int a, k;
            cin >> a >> k;
            op[i] = {-1, ptr++, a, k};
            Sor[a].push_back(i);
        }
    }

    vector<int> ans(ptr, -1);

    for (int i = 1; i <= n; i++) {
        for (int ind : Open[i]) {
            if (op[ind][3] == -1) {
                segTree.update(1, 0, q, ind, q, -op[ind][2]);
                fenwickTree.add(ind, op[ind][2], 1);
            } else {
                segTree.update(1, 0, q, ind, q, op[ind][2]);
                fenwickTree.add(ind, op[ind][2], 0);
            }
        }

        for (int ind : Close[i]) {
            if (op[ind][3] == -1) {
                segTree.update(1, 0, q, ind, q, op[ind][2]);
                fenwickTree.add(ind, -op[ind][2], 1);
            } else {
                segTree.update(1, 0, q, ind, q, -op[ind][2]);
                fenwickTree.add(ind, -op[ind][2], 0);
            }
        }

        for (int ind : Sor[i]) {
            Info X = segTree.query(1, 0, q, 0, ind);
            if (X.mn >= 0) X.ind = 0;

            int xd = fenwickTree.get(X.ind, 0);
            xd += fenwickTree.get(ind, 1) - fenwickTree.get(X.ind, 1);
            xd += op[ind][3];

            if (xd > fenwickTree.get(ind, 0) || fenwickTree.get(ind, 0) == 0) {
                ans[op[ind][1]] = 0;
                continue;
            }

            int hangi = fenwickTree.bs(xd);

            if (op[hangi][3] == -1 || op[hangi][0] == -1 || hangi > q || fenwickTree.get(hangi, 0) < xd) ans[op[ind][1]] = 0;
            else ans[op[ind][1]] = op[hangi][3];
        }
    }

    for (int i = 0; i < ptr; i++) cout << ans[i] << '\n';
}

int32_t main() {
    cin.tie(0); ios::sync_with_stdio(0);
    int tc = 1;
    while (tc--) solve();
    return 0;
}

• 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