Submission #386986

#	Time	Username	Problem	Language	Result	Execution time	Memory
386986		keko37	Food Court (JOI21_foodcourt)	C++14	68 / 100	388 ms	47524 KiB

foodcourt

#include<bits/stdc++.h>

using namespace std;

typedef long long llint;
typedef pair <llint, llint> pi;

const int MAXN = 250005;

int n, m, q, ofs = 1;
llint tip[MAXN], lef[MAXN], rig[MAXN], k[MAXN], col[MAXN], sol[MAXN];
pi t[MAXN * 4]; llint sum[MAXN];
vector <pi> v[MAXN];
vector <int> u[MAXN];

pi spoji (pi a, pi b) {
    return {a.first + b.first, max(a.second + b.first, b.second)};
}

void update (int pos, llint val) {
    pos += ofs;
    t[pos].first += val;
    t[pos].second = max(t[pos].first, 0LL);
    sum[pos] = t[pos].second;
    pos /= 2;
    while (pos > 0) {
        t[pos] = spoji(t[pos * 2], t[pos * 2 + 1]);
        sum[pos] = sum[2 * pos] + sum[2 * pos + 1];
        pos /= 2;
    }
}

pi upit (int x, int from, int to, int lo, int hi) {
    if (from <= lo && hi <= to) return t[x];
    if (to < lo || hi < from) return {0, 0};
    return spoji(upit(2 * x, from, to, lo, (lo + hi) / 2), upit(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi));
}

int nadi (int x, llint val) {
    if (x >= ofs) return x;
    if (val <= sum[2 * x + 1]) return nadi(2 * x + 1, val);
    return nadi(2 * x, val - sum[2 * x + 1]);
}

int bs (int pos, llint val) {
    int curr = pos + ofs;
    llint curr_sum = sum[curr];
    if (val <= curr_sum) return pos;
    while (curr > 1) {
        if (curr % 2 == 0) {
            curr /= 2;
        } else {
            if (val > curr_sum + sum[curr - 1]) {
                curr_sum += sum[curr - 1];
                curr /= 2;
            } else {
                return nadi(curr - 1, val - curr_sum) - ofs;
            }
        }
    }
    return 0;
}

void get_curr_siz () {
    for (int i = 1; i <= q; i++) {
        if (tip[i] == 1) {
            v[lef[i]].push_back({k[i], i});
            v[rig[i] + 1].push_back({-k[i], i});
        } else if (tip[i] == 2) {
            v[lef[i]].push_back({-k[i], i});
            v[rig[i] + 1].push_back({k[i], i});
        } else {
            u[lef[i]].push_back(i);
        }
    }
    while (ofs < q + 1) ofs *= 2;
    for (int pos = 1; pos <= n; pos++) {
        for (auto pp : v[pos]) {
            llint val = pp.first;
            int ind = pp.second;
            update(ind, val);
        }
        for (auto i : u[pos]) {
            llint siz = upit(1, 0, i, 0, ofs - 1).second;
            if (k[i] <= siz) {
                sol[i] = col[bs(i, siz - k[i] + 1)];
            }
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= q; i++) {
        cin >> tip[i];
        if (tip[i] == 1) {
            cin >> lef[i] >> rig[i] >> col[i] >> k[i];
        } else if (tip[i] == 2) {
            cin >> lef[i] >> rig[i] >> k[i];
        } else {
            cin >> lef[i] >> k[i];
        }
    }
    get_curr_siz();
    for (int i = 1; i <= q; i++) {
        if (tip[i] != 3) continue;
        cout << sol[i] << '\n';
    }
    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 0 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 0 / 11