Submission #813443

#	Time	Username	Problem	Language	Result	Execution time	Memory
813443		ParsaS	Food Court (JOI21_foodcourt)	C++17	2 / 100	61 ms	32996 KiB

foodcourt

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 25e4 + 5;
int n, m, q;
int C[N];
vector<int> vadd[N], vrem[N], vec;
vector<pair<int, int > > qr[N];
int ans[N];
int S[N << 2];

struct node {
    int rem, cnt, ex;
    node() {
        rem = cnt = ex = 0;
    }
    void clear() {
        cnt = rem = ex = 0;
    }
} seg[N << 2];

void shift(int v, int tl, int tr) {
    if (tl == tr)
        return;
    int lc = v << 1, rc = v << 1 | 1;
    seg[lc].ex += max(0, seg[v].ex - seg[lc].cnt);
    seg[lc].rem += seg[v].rem + min(seg[v].ex, seg[lc].cnt);
    seg[lc].cnt = seg[v].cnt + max(0, seg[lc].cnt - seg[v].ex);
    seg[rc].ex += max(0, seg[v].ex - seg[rc].cnt);
    seg[rc].rem += seg[v].rem + min(seg[v].ex, seg[rc].cnt);
    seg[rc].cnt = seg[v].cnt + max(0, seg[rc].cnt - seg[v].ex);

    seg[v].clear();
}

void ADD(int l, int r, int c, int v = 1, int tl = 1, int tr = n) {
    shift(v, tl, tr);
    if (l > tr || r < tl)
        return;
    if (tl >= l && tr <= r) {
        seg[v].cnt += c;
        return;
    }
    int mid = (tl + tr) >> 1;
    ADD(l, r, c, v << 1, tl, mid);
    ADD(l, r, c, v << 1 | 1, mid + 1, tr);
}
void REM(int l, int r, int c, int v = 1, int tl = 1, int tr = n) {
    shift(v, tl, tr);
    if (l > tr || r < tl) {
        return;
    }
    if (tl >= l && tr <= r) {
        if (tl == tr) {
            int k = min(seg[v].cnt, c);
            seg[v].cnt -= k;
            seg[v].rem += k;
            seg[v].ex += c - k;
        }
        else
            seg[v].ex += c;
        return;
    }
    int mid = (tl + tr) >> 1;
    REM(l, r, c, v << 1, tl, mid);
    REM(l, r, c, v << 1 | 1, mid + 1, tr);
}
node query(int i, int v = 1, int tl = 1, int tr = n) {
    shift(v, tl, tr);
    if (tl == tr) {
        return seg[v];
    }
    int mid = (tl + tr) >> 1;
    if (i <= mid)
        return query(i, v << 1, tl, mid);
    return query(i, v << 1 | 1, mid + 1, tr);
}

void upd(int i, int val, int v = 1, int tl = 0, int tr = (int)vec.size()) {
    if (tl == tr) {
        S[v] += val;
        return;
    }
    int mid = (tl + tr) >> 1;
    if (i <= mid)
        upd(i, val, v << 1, tl, mid);
    else
        upd(i, val, v << 1 | 1, mid + 1, tr);
    S[v] = S[v << 1] + S[v << 1 | 1];
}
int query2(int x, int v = 1, int tl = 0, int tr = (int)vec.size()) {
    if (tl == tr)
        return tl;
    int mid = (tl + tr) >> 1;
    if (S[v << 1] >= x)
        return query2(x, v << 1, tl, mid);
    return query2(x - S[v << 1], v << 1 | 1, mid + 1, tr);
}


void solve() {
    cin >> n >> m >> q;
    for (int i = 0; i < q; i++) {
        ans[i] = -1;
        int t; cin >> t;
        if (t == 1) {
            int l, r, c, k; cin >> l >> r >> k >> c;
            C[(int)vec.size()] = c;
            vadd[l].pb((int)vec.size());
            vrem[r + 1].pb((int)vec.size());
            vec.pb(k);

            ADD(l, r, c);
        }
        else if (t == 2) {
            int l, r, c; cin >> l >> r >> c;
            REM(l, r, c);

        }
        else {
            int a, b; cin >> a >> b;
            node v = query(a);
            if (v.cnt < b) {
                ans[i] = 0;
            }
            else {
                qr[a].pb(mp(v.rem + b, i));
            }
        }
        continue;
        for (int j = 1; j <= n; j++) {
            node u = query(j);
            cout << u.cnt << ' ';
        }
        cout << endl;
        node u = query(1);
        cout << u.cnt << ' ' << u.rem << ' ' << u.ex << endl;
    }
    for (int i = 1; i <= n; i++) {
        for (auto x : vadd[i]) {
            upd(x, C[x]);
        }
        for (auto x : vrem[i]) {
            upd(x, -C[x]);
        }
        for (auto [c, j] : qr[i]) {
            ans[j] = vec[query2(c)];
        }
    }
    for (int i = 0; i < q; i++) {
        if (ans[i] != -1)
            cout << ans[i] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
}

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