Submission #1098084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098084		_callmelucian	Food Court (JOI21_foodcourt)	C++14	13 / 100	1051 ms	233064 KiB

foodcourt

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,ll> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 250005;

struct IT {
    vector<ll> lo, hi, lazy;
    IT (int sz) : lo(4 * sz), hi(4 * sz), lazy(4 * sz) {}

    void apply (int k, ll val) {
        lo[k] += val, hi[k] += val, lazy[k] += val;
    }

    void pushDown (int k) {
        if (!lazy[k]) return;
        apply(2 * k, lazy[k]), apply(2 * k + 1, lazy[k]), lazy[k] = 0;
    }

    void update (int a, int b, ll val, int k, int l, int r) {
        if (b < l || r < a) return;
        if (a <= l && r <= b)
            return apply(k, val), void();
        pushDown(k);
        int mid = (l + r) >> 1;
        update(a, b, val, 2 * k, l, mid);
        update(a, b, val, 2 * k + 1, mid + 1, r);
        lo[k] = min(lo[2 * k], lo[2 * k + 1]);
        hi[k] = max(hi[2 * k], hi[2 * k + 1]);
    }

    void walk (ll cur, int k, int l, int r, vector<tt> &vec) {
        if (lo[k] >= cur || hi[k] == 0) return;
        if (l == r)
            return vec.emplace_back(l, r, lo[k]), void();
        pushDown(k);
        int mid = (l + r) >> 1;
        walk(cur, 2 * k, l, mid, vec);
        walk(cur, 2 * k + 1, mid + 1, r, vec);
    }

    void breakDown (int a, int b, ll cur, int k, int l, int r, vector<tt> &vec) {
        if (b < l || r < a) return;
        if (lo[k] >= cur || hi[k] == 0) return;
        if (a <= l && r <= b)
            return walk(cur, k, l, r, vec), void();
        pushDown(k);
        int mid = (l + r) >> 1;
        breakDown(a, b, cur, 2 * k, l, mid, vec);
        breakDown(a, b, cur, 2 * k + 1, mid + 1, r, vec);
    }
} tree(mn);

struct BIT {
    vector<ll> tr;
    BIT (int sz) : tr(sz + 1) {}

    int p (int k) { return k & -k; }

    void update (int pos, int val) {
        for (; pos < tr.size(); pos += p(pos)) tr[pos] += val;
    }

    ll preSum (int pos) {
        ll ans = 0;
        for (; pos; pos -= p(pos)) ans += tr[pos];
        return ans;
    }

    int walk (ll ub) {
        int ans = 0, lg = 31 - __builtin_clz(tr.size());
        ll sum = 0;
        for (int msk = (1 << lg); msk > 0; msk >>= 1) {
            if ((ans | msk) < tr.size() && tr[ans | msk] + sum < ub) ans |= msk, sum += tr[ans];
        }
        return ans;
    }
} customer(mn), cut(mn);

vector<pl> openCust[mn], openCut[mn], closeCust[mn], closeCut[mn], query[mn];
int group[mn], ans[mn];

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

    int n, m, q; cin >> n >> m >> q;
    for (int i = 1; i <= q; i++) {
        int type; cin >> type;
        if (type == 1) {
            int l, r; ll ppl; cin >> l >> r >> group[i] >> ppl;
            openCust[l].emplace_back(i, ppl);
            closeCust[r].emplace_back(i, ppl);
            tree.update(l, r, ppl, 1, 1, n);
        }
        else if (type == 2) {
            int l, r; ll cut; cin >> l >> r >> cut;
            vector<tt> updates;
            tree.breakDown(l, r, cut, 1, 1, n, updates);

            int sz = updates.size();
            for (int i = 0; i < sz; i++) {
                int curL, curR; ll w; tie(curL, curR, w) = updates[i];
                if (l < curL) updates.emplace_back(l, curL - 1, cut);
                l = curR + 1;
            }
            if (l <= r) updates.emplace_back(l, r, cut);

            for (auto [l, r, w] : updates) {
                openCut[l].emplace_back(i, w);
                closeCut[r].emplace_back(i, w);
                tree.update(l, r, -w, 1, 1, n);
            }
        }
        else {
            int pos; ll ppl; cin >> pos >> ppl;
            query[pos].emplace_back(i, ppl);
        }
        ans[i] = -1;
    }

    for (int i = 1; i <= n; i++) {
        for (auto [crew, sz] : openCust[i])
            customer.update(crew, sz);
        for (auto [crew, sz] : openCut[i])
            cut.update(crew, sz);

        for (auto [moment, ppl] : query[i]) {
            ll curCustomer = customer.preSum(moment), leftCustomer = cut.preSum(moment);
            if (curCustomer - leftCustomer < ppl) ans[moment] = 0;
            else {
                int crew = customer.walk(leftCustomer + ppl) + 1;
                ans[moment] = group[crew];
            }
        }

        for (auto [crew, sz] : closeCust[i])
            customer.update(crew, -sz);
        for (auto [crew, sz] : closeCut[i])
            cut.update(crew, -sz);
    }

    for (int i = 1; i <= q; i++)
        if (ans[i] != -1) cout << ans[i] << "\n";

    return 0;
}

Compilation message (stderr)

foodcourt.cpp: In member function 'void BIT::update(int, int)':
foodcourt.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (; pos < tr.size(); pos += p(pos)) tr[pos] += val;
      |                ~~~~^~~~~~~~~~~
foodcourt.cpp: In member function 'int BIT::walk(ll)':
foodcourt.cpp:82:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             if ((ans | msk) < tr.size() && tr[ans | msk] + sum < ub) ans |= msk, sum += tr[ans];
      |                 ~~~~~~~~~~~~^~~~~~~~~~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:118:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |             for (auto [l, r, w] : updates) {
      |                       ^
foodcourt.cpp:132:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  132 |         for (auto [crew, sz] : openCust[i])
      |                   ^
foodcourt.cpp:134:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  134 |         for (auto [crew, sz] : openCut[i])
      |                   ^
foodcourt.cpp:137:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  137 |         for (auto [moment, ppl] : query[i]) {
      |                   ^
foodcourt.cpp:146:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  146 |         for (auto [crew, sz] : closeCust[i])
      |                   ^
foodcourt.cpp:148:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  148 |         for (auto [crew, sz] : closeCut[i])
      |                   ^

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