Submission #390299

#	Time	Username	Problem	Language	Result	Execution time	Memory
390299		apostoldaniel854	Food Court (JOI21_foodcourt)	C++14	100 / 100	613 ms	66784 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define dbg(x) cerr << #x << " " << x << "\n"

struct node_t {
    ll sum_max;
    ll sum;
};

class segtree {
public:
    vector <node_t> seg;
    int n;
    segtree (int n) {
        this->n = n;
        seg.resize (1 + 4 * n);
    }
    node_t combine (node_t lnode, node_t rnode) {
        return {
            max (rnode.sum_max, rnode.sum + lnode.sum_max),
            lnode.sum + rnode.sum
        };
    }
    void update (int node, int lb, int rb, int pos, ll val) {
        if (lb == rb) {
            seg[node] = {max (0ll, val), val};
            return;
        }
        int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1;
        if (pos <= mid)
            update (lnode, lb, mid, pos, val);
        else
            update (rnode, mid + 1, rb, pos, val);
        seg[node] = combine (seg[lnode], seg[rnode]);
    }
    node_t query (int node, int lb, int rb, int ql, int qr) {
        if (ql <= lb && rb <= qr) {
            return seg[node];
        }
        int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1;
        node_t ans = {0, 0};
        if (ql <= mid)
            ans = combine (ans, query (lnode, lb, mid, ql, qr));
        if (qr > mid)
            ans = combine (ans, query (rnode, mid + 1, rb, ql, qr));
        return ans;
    }
};
class fenwick {
public:
    vector <ll> aib;
    int n;
    fenwick (int n) {
        this->n = n;
        aib.resize (1 + n);
    }
    void upd (int pos, ll val) {
        while (pos <= n) {
            aib[pos] += val;
            pos += pos & -pos;
        }
    }
    ll qry (int pos) {
        ll ans = 0;
        while (pos > 0) {
            ans += aib[pos];
            pos -= pos & -pos;
        }
        return ans;
    }
    ll qry (int l, int r) {
        return qry (r) - qry (l - 1);
    }
    int kth (ll k) {
        int ans = 0;
        for (int step = (1 << 20); step > 0; step /= 2)
            if (ans + step <= n && aib[ans + step] < k) {
                ans += step;
                k -= aib[ans];
            }
        return ans + 1;
    }
};

const int MAX_N = 25e4;

vector <pair <ll, ll>> qry[1 + MAX_N], upd_seg[1 + MAX_N], upd_fen[1 + MAX_N]; /// first-> pos, second-> value
ll group[1 + MAX_N];
ll sol[1 + MAX_N];

int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= q; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            ll l, r, c, k;
            cin >> l >> r >> c >> k;
            group[i] = c;
            upd_seg[l].push_back ({i, k});
            if (r < n)
                upd_seg[r + 1].push_back ({i, 0});
            upd_fen[l].push_back ({i, k});
            if (r < n)
                upd_fen[r + 1].push_back ({i, -k});
        }
        else if (type == 2) {
            ll l, r, k;
            cin >> l >> r >> k;
            upd_seg[l].push_back ({i, -k});
            if (r < n)
                upd_seg[r + 1].push_back ({i, 0});
        }
        else {
            ll a, b;
            cin >> a >> b;
            qry[a].push_back ({i, b});
        }
    }
    segtree balance (q);
    fenwick all (q);
    for (int i = 0; i <= q; i++)
        sol[i] = -1;
    for (int i = 1; i <= n; i++) {
        for (auto it : upd_seg[i])
            balance.update (1, 1, q, it.first, it.second);
        for (auto it : upd_fen[i])
            all.upd (it.first, it.second);
        for (auto it : qry[i]) {
            ll best = balance.query (1, 1, q, 1, it.first).sum_max;
            if (best >= it.second) {
                sol[it.first] = group[all.kth (all.qry (it.first) - (best - it.second))];
            }
            else {
                sol[it.first] = 0;
            }
        }
    }
    for (int i = 1; i <= q; i++)
        if (sol[i] >= 0)
            cout << sol[i] << "\n";
    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