Submission #1098863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098863		_callmelucian	Food Court (JOI21_foodcourt)	C++14	100 / 100	364 ms	72528 KiB

foodcourt

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

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

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

const int mn = 2e5 + 5e4 + 4;

struct node {
    ll neg, val;

    node() : neg(0), val(0) {}
    node (ll neg, ll val) : neg(neg), val(val) {}

    node operator + (const node &o) const {
        ll delta = val - o.neg;
        return node(neg - min(0LL, delta), o.val + max(0LL, delta));
    }
};

struct IT {
    vector<node> tr;
    IT (int sz) : tr(4 * sz) {}

    void update (int pos, ll val, int k, int l, int r) {
        if (pos < l || r < pos) return;
        if (l == r) {
            if (val < 0) tr[k] = node(-val, 0);
            else tr[k] = node(0, val);
            return;
        }
        int mid = (l + r) >> 1;
        update(pos, val, 2 * k, l, mid);
        update(pos, val, 2 * k + 1, mid + 1, r);
        tr[k] = tr[2 * k] + tr[2 * k + 1];
    }

    node query (int a, int b, int k, int l, int r) {
        if (b < l || r < a) return node(0, 0);
        if (a <= l && r <= b) return tr[k];
        int mid = (l + r) >> 1;
        return query(a, b, 2 * k, l, mid) + query(a, b, 2 * k + 1, mid + 1, r);
    }
} tree(mn);

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

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

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

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

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

vector<ll> openPush[mn], closePush[mn], openPop[mn], closePop[mn], query[mn];
ll group[mn], population[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; cin >> l >> r >> group[i] >> population[i];
            openPush[l].push_back(i);
            closePush[r].push_back(i);
        }
        else if (type == 2) {
            int l, r; cin >> l >> r >> population[i];
            openPop[l].push_back(i);
            closePop[r].push_back(i);
        }
        else {
            int pos; cin >> pos >> population[i];
            query[pos].push_back(i);
        }
        ans[i] = -1;
    }

    for (int i = 1; i <= n; i++) {
        for (int u : openPush[i]) {
            customer.update(u, population[u]);
            tree.update(u, population[u], 1, 1, q);
        }
        for (int u : openPop[i])
            tree.update(u, -population[u], 1, 1, q);

        for (int moment : query[i]) {
            ll allCustomer = customer.preSum(moment), actual = tree.query(1, moment, 1, 1, q).val;
            ll leave = allCustomer - actual;
            if (population[moment] + leave <= allCustomer)
                ans[moment] = group[customer.walk(population[moment] + leave)];
            else ans[moment] = 0;
        }

        for (int u : closePush[i]) {
            customer.update(u, -population[u]);
            tree.update(u, 0, 1, 1, q);
        }
        for (int u : closePop[i])
            tree.update(u, 0, 1, 1, q);
    }
    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, ll)':
foodcourt.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         for (; k < tr.size(); k += p(k)) tr[k] += val;
      |                ~~^~~~~~~~~~~
foodcourt.cpp: In member function 'int BIT::walk(ll)':
foodcourt.cpp:69:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             if ((ans | mask) < tr.size() && tr[ans | mask] + sum < ub) ans |= mask, sum += tr[ans];
      |                 ~~~~~~~~~~~~~^~~~~~~~~~~

• 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