Submission #892136

#	Time	Username	Problem	Language	Result	Execution time	Memory
892136		box	Food Court (JOI21_foodcourt)	C++17	100 / 100	293 ms	42940 KiB

foodcourt

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

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int N = 2.5e5+5, M = 2.5e5+5, Q = 2.5e5+5;
const int N_ = 1 << 18;

int n, m, q;
int who[M];
vector<pair<int, int>> upd_add[N], upd_rem[N];
vector<pair<int, i64>> qry[N];
int ans[Q];

struct {
    i64 sum[N_ * 2];
    void upd(int i, int x) {
        sum[i += N_] = x;
        while (i /= 2) sum[i] = sum[i * 2] + sum[i * 2 + 1];
    }
    i64 qry(int l, int r) {
        i64 x = 0;
        for (l += N_, r += N_; l <= r; l /= 2, r /= 2) {
            if (l & 1) x += sum[l++];
            if (~r & 1) x += sum[r--];
        }
        return x;
    }
    i64 walk(i64 x) {
        int i = 0;
        x--;
        while (i < N_) {
            if (sum[i * 2] <= x) {
                x -= sum[i * 2];
                i = i * 2 + 1;
            } else i *= 2;
        }
        return i - N_;
    }
} seg_s;

typedef ar<i64, 2> T;

T operator+(const T one, const T two) {
    return {one[0] + two[0], max(one[1] + two[0], two[1])};
}

struct {
    T info[N_ * 2];
    void upd(int i, int x) {
        info[i += N_] = T{x, max(0, x)};
        while (i /= 2) info[i] = info[i * 2] + info[i * 2 + 1];
    }
    T qry(int l, int r) {
        T xl{0, 0}, xr{0, 0};
        for (l += N_, r += N_; l <= r; l /= 2, r /= 2) {
            if (l & 1) xl = xl + info[l++];
            if (~r & 1) xr = info[r--] + xr;
        }
        return xl + xr;
    }
} seg_k;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> q;
    for (int h = 0; h < q; h++) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r, c, k;
            cin >> l >> r >> c >> k, l--, r--;
            who[h] = c;
            upd_add[l].push_back({h, k});
            upd_add[r + 1].push_back({h, 0});
        } else if (t == 2) {
            int l, r, k;
            cin >> l >> r >> k, l--, r--;
            upd_rem[l].push_back({h, k});
            upd_rem[r + 1].push_back({h, 0});
        } else {
            int i; i64 k;
            cin >> i >> k, i--;
            qry[i].push_back({h, k});
        }
        ans[h] = -1;
    }
    for (int i = 0; i < n; i++) {
        for (auto [h, k] : upd_add[i]) {
            seg_s.upd(h, k);
            seg_k.upd(h, k);
        }
        for (auto [h, k] : upd_rem[i]) {
            seg_k.upd(h, -k);
        }
        for (auto [h, k] : qry[i]) {
            i64 num_left = seg_k.qry(0, h)[1];
            i64 total = seg_s.qry(0, h);
            ans[h] = num_left < k ? 0 : who[seg_s.walk(total - num_left + k)];
        }
    }
    for (int h = 0; h < q; h++) if (~ans[h]) cout << ans[h] << '\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