Submission #1065615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065615		phoenix	Food Court (JOI21_foodcourt)	C++17	24 / 100	149 ms	40276 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = (1 << 18);

#define cerr if (false) cout

struct node {
    ll sum = 0;
    ll pre = 0;
};
node tr[2 * N];

node combine(node a, node b) {
    node res;
    res.sum = a.sum + b.sum;
    res.pre = min(a.pre, a.sum + b.pre);
    return res;
}

void update(int pos, ll val) {
    // cerr << "upd: " << pos << ' ' << val << '\n';
    tr[pos += N] = {val, min(0ll, val)};
    for (pos >>= 1; pos; pos >>= 1) 
        tr[pos] = combine(tr[2 * pos], tr[2 * pos + 1]);
    // cerr << "tree: " << tr[1].sum << ' ' << tr[1].pre << '\n';
}
node get(int ql, int qr, int l = 0, int r = N - 1, int v = 1) {
    if (r < ql || l > qr)
        return node();
    if (ql <= l && r <= qr) 
        return tr[v];
    int m = (l + r) / 2;
    return combine(get(ql, qr, l, m, 2 * v), get(ql, qr, m + 1, r, 2 * v + 1)); 
}

ll cnt[2 * N];
void add(int v, ll a) {
    for (cnt[v += N] += a; v > 1; v >>= 1)
        cnt[v >> 1] = cnt[v] + cnt[v^1];
}
ll count(int ql, int qr, int l = 0, int r = N - 1, int v = 1) {
    if (r < ql || l > qr)   
        return 0;
    if (ql <= l && r <= qr)
        return cnt[v];
    int m = (l + r) / 2;
    return count(ql, qr, l, m, 2 * v) + count(ql, qr, m + 1, r, 2 * v + 1);
}

int n, m, q;

vector<pair<int, ll>> join[N][2];
vector<pair<int, ll>> leave[N][2];
vector<pair<int, ll>> service[N];  

map<int, int> timeToGroup;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int t = 1; t <= q; t++) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r, k, c;
            cin >> l >> r >> c >> k;
            timeToGroup[t] = c;
            join[l][0].push_back({t, k});
            join[r][1].push_back({t, k});
        }
        if (type == 2) {
            int l, r, k;
            cin >> l >> r >> k;
            leave[l][0].push_back({t, k});
            leave[r][1].push_back({t, k});
        }
        if (type == 3) {
            int a, b;
            cin >> a >> b;
            service[a].push_back({t, b});
        }
    }
    
    vector<int> res(q + 1, -2);

    for (int i = 1; i <= n; i++) {
        for (auto o : join[i][0]) {
            int t = o.first, k = o.second;
            update(t, +k);
            add(t, +k);
        }
        for (auto o : leave[i][0]) {
            int t = o.first, k = o.second;
            update(t, -k);
        }
        for (auto [t, b] : service[i]) {
            ll num = get(1, t).sum - get(1, t).pre;
            if (num < b) {
                res[t] = 0;
                continue;
            }
            int l = 0, r = t + 1;
            while (r - l > 1) {
                int m = (l + r) / 2;
                if (count(m, t) >= num - b + 1)
                    l = m;
                else 
                    r = m;
            }
            res[t] = timeToGroup[l];
        }
        for (auto o : join[i][1]) {
            int t = o.first, k = o.second;
            update(t, 0);
            add(t, -k);
        }
        for (auto o : leave[i][1]) {
            int t = o.first, k = o.second;
            update(t, 0);
        }
    }
    for (int i = 1; i <= q; i++) {
        if (res[i] != -2)
            cout << res[i] << '\n';
    }
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:122:30: warning: unused variable 'k' [-Wunused-variable]
  122 |             int t = o.first, k = o.second;
      |                              ^

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