Submission #1118571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118571		Sharky	Food Court (JOI21_foodcourt)	C++17	100 / 100	554 ms	60080 KiB

foodcourt

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

#define int long long
const int N = 2.5e5 + 10;

vector<pair<int, int>> qry[N], ev[N]; // ev: index, cnt
int qc = 0, ans[N], grp[N];

struct Node {
    int pmin = 0, sum = 0, add = 0;
} dummy;

struct SegTree {
    int size = 1;
    vector<Node> seg, lazy;
    void init(int n) {
        while (size < n) size *= 2;
        seg.assign(2 * size + 10, dummy);
        lazy.assign(2 * size + 10, dummy);
    }
    void push(int id) {
        seg[id].pmin = min(seg[id].pmin, seg[id].sum + lazy[id].pmin);
        seg[id].sum += lazy[id].sum;
        seg[id].add += lazy[id].add;
        if (id < size) for (int i = 0; i < 2; i++) {
            lazy[id * 2 + i].pmin = min(lazy[id * 2 + i].pmin, lazy[id * 2 + i].sum + lazy[id].pmin);
            lazy[id * 2 + i].sum += lazy[id].sum;
            lazy[id * 2 + i].add += lazy[id].add;
        }
        lazy[id].sum = lazy[id].pmin = lazy[id].add = 0;
    }
    void update(int ql, int qr, int v, int l, int r, int id) {
        push(id);
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            lazy[id].add = max(0LL, v);
            lazy[id].sum = v;
            lazy[id].pmin = min(0LL, v);
            push(id);
            return;
        }
        int mid = (l + r) / 2;
        update(ql, qr, v, l, mid, id * 2);
        update(ql, qr, v, mid + 1, r, id * 2 + 1);
    }
    Node query(int pos, int l, int r, int id) {
        push(id);
        if (l == r) return seg[id];
        int mid = (l + r) / 2;
        if (pos <= mid) return query(pos, l, mid, id * 2);
        return query(pos, mid + 1, r, id * 2 + 1);
    }
} ST;

struct SegTreeWalk {
    int size = 1;
    vector<int> seg;
    void init(int n) {
        while (size < n) size *= 2;
        seg.assign(2 * size + 10, 0);
    }
    void update(int pos, int val, int l, int r, int id) {
        if (l == r) {
            seg[id] += val;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) update(pos, val, l, mid, id * 2);
        else update(pos, val, mid + 1, r, id * 2 + 1);
        seg[id] = seg[id * 2] + seg[id * 2 + 1];
    }
    int find(int x, int l, int r, int id) {
        if (seg[id] < x) return 0;
        if (l == r) return l;
        int mid = (l + r) / 2;
        if (seg[id * 2] >= x) return find(x, l, mid, id * 2);
        return find(x - seg[id * 2], mid + 1, r, id * 2 + 1);
    }
} seg;

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    ST.init(n+1);
    seg.init(q+1);
    for (int i = 1; i <= q; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            grp[i] = c;
            ST.update(l, r, k, 1, n, 1);
            ev[l].push_back({i, k});
            ev[r+1].push_back({i, -k});
        } else if (type == 2) {
            int l, r, k;
            cin >> l >> r >> k;
            ST.update(l, r, -k, 1, n, 1);
        } else {
            int id, x;
            cin >> id >> x;
            ++qc;
            auto [pmin, sum, add] = ST.query(id, 1, n, 1);
            if (sum - pmin >= x) qry[id].push_back({add - sum + pmin + x, qc});
        }
    }
    for (int i = 1; i <= n; i++) {
        for (auto& [id, add] : ev[i]) seg.update(id, add, 1, q, 1);
        for (auto& [k, id] : qry[i]) ans[id] = grp[seg.find(k, 1, q, 1)];
    }
    for (int i = 1; i <= qc; 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