Submission #728619

#	Time	Username	Problem	Language	Result	Execution time	Memory
728619		piOOE	Food Court (JOI21_foodcourt)	C++17	100 / 100	418 ms	53496 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

namespace SegmentTree {
    constexpr int N = 1 << 18;
    array<ll, 2> t[N * 2];

    array<ll, 2> operator+(const array<ll, 2> &a, const array<ll, 2> &b) {
        return {a[0] + b[0], max(b[1], a[1] + b[0])};
    }

    void pull(int x) {
        t[x] = t[x << 1] + t[x << 1 | 1];
    }

    void modify(int x, ll v) {
        x += N;
        t[x][0] = v, t[x][1] = max(0LL, v);
        while (x >>= 1) {
            pull(x);
        }
    }

    array<ll, 2> rangeQuery(int l, int r) {
        array<ll, 2> L{}, R{};
        for (l += N, r += N; l < r; r >>= 1, l >>= 1) {
            if (l & 1) {
                L = L + t[l++];
            }
            if (r & 1) {
                R = t[--r] + R;
            }
        }
        return L + R;
    }
}

template<typename T>
struct Fenwick {
    int n;
    vector<T> a;

    Fenwick() = default;

    explicit Fenwick(int n) : n(n), a(n + 1) {}

    void modify(int x, T v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i] += v;
        }
    }

    void modify(int l, int r, T v) {
        if (l >= r) return;
        modify(l, v), modify(r, -v);
    }

    T sum(int x) {
        T ans = 0;
        for (int i = x + 1; i > 0; i -= i & -i) {
            ans += a[i];
        }
        return ans;
    }

    T rangeSum(int l, int r) { //[l, r)
        if (l >= r) return 0;
        return sum(r - 1) - sum(l - 1);
    }

    int kth(T k) {
        int x = 0;
        for (int i = 1 << __lg(n); i; i >>= 1) {
            if (x + i <= n && k > a[x + i]) {
                x += i;
                k -= a[x];
            }
        }
        return x;
    }
};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<int>> qr(n + 1), ql(n), que(n);
    vector<ll> L(q), R(q), ans(q), K(q);

    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t >> L[i] >> R[i];
        L[i] -= 1;

        if (t == 1 || t == 2) {
            ql[L[i]].push_back(i);
            qr[R[i]].push_back(i);
        } else if (t == 3) {
            que[L[i]].push_back(i);
        }

        if (t == 1) {
            cin >> R[i] >> K[i];
        } else if (t == 2) {
            cin >> K[i];
            K[i] = -K[i];
        } else {
            L[i] = -1;
        }
    }

    Fenwick<ll> fn(q);

    for (int i = 0; i < n; ++i) {
        for (int j : qr[i]) {
            SegmentTree::modify(j, 0);
            if (K[j] > 0) {
                fn.modify(j, -K[j]);
            }
        }

        for (int j : ql[i]) {
            SegmentTree::modify(j, K[j]);
            if (K[j] > 0) {
                fn.modify(j, K[j]);
            }
        }

        for (int j : que[i]) {
            ll have = SegmentTree::rangeQuery(0, j)[1];
            if (have >= R[j]) {
                ans[j] = R[fn.kth(fn.sum(j) - (have - R[j]))];
            }
        }
    }

    for (int i = 0; i < q; ++i) {
        if (L[i] == -1) {
            cout << ans[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