Submission #922120

#	Time	Username	Problem	Language	Result	Execution time	Memory
922120		406	Food Court (JOI21_foodcourt)	C++17	100 / 100	422 ms	56476 KiB

foodcourt

    #include <bits/stdc++.h>
    using namespace std;
    //#define int long long
    using ll = long long;
    #define FOR(i, a, b) for (int i = (a); i < (b); i++) 
    const int64_t INF = 1ll << 60;
    const int N = 2.6e5;
    const int LG = 17;
    long long B[N], mn[N << 2], delta[N << 2];
    vector<array<int, 2>> ad[N], del[N];
    vector<array<ll, 2>> GET[N];
    short t[N];
    int L[N], R[N], C[N], A[N], n, m, q, ans[N], K[N];
     
    struct fenw {
            long long bit[N];
            void add(int r, int d) {
                    r++;
                    for (; r < N; r += r & -r)
                            bit[r] += d;
            }
            long long get(int r) {
                    r++;
                    long long re = 0;
                    for (; r; r &= (r - 1)) 
                            re += bit[r];
                    return re;
            }
            int find(long long x) {
                    int pos = 0;
                    for (int i = LG; i >= 0; i--) {
                            if ((pos | (1 << i)) < N && bit[pos | (1 << i)] < x) {
                                    pos |= 1 << i;
                                    x -= bit[pos];
                            }
                    }
                    return pos;
            }
    } pos, all;
     
    void add(int v, int l, int r, int L, int R, int d) {
            if (L <= l && r <= R) {
                    mn[v] += d;
                    delta[v] += d;
                    return;
            }
            int m = l + r >> 1;
            if (R <= m)
                    add(v << 1, l, m, L, R, d);
            else if (L >= m)
                    add(v << 1 | 1, m, r, L, R, d);
            else {
                    add(v << 1, l, m, L, R, d);
                    add(v << 1 | 1, m, r, L, R, d);
            }
            mn[v] = min(mn[v << 1], mn[v << 1 | 1]) + delta[v];
    }
    ll get(int v, int l, int r, int L, int R) {
            if (L <= l && r <= R) return mn[v];
            int m = l + r >> 1;
            if (R <= m)
                    return get(v << 1, l, m, L, R) + delta[v];
            else if (L >= m)
                    return get(v << 1 | 1, m, r, L, R) + delta[v];
            else 
                    return min(get(v << 1, l, m, L, R), get(v << 1 | 1, m, r, L, R)) + delta[v];
    }
     
    signed main() {
            ios::sync_with_stdio(0), cin.tie(0);
            cin >> n >> m >> q;
            FOR(i, 0, q) {
                    cin >> t[i];
                    if (t[i] == 1) {
                            cin >> L[i] >> R[i] >> C[i] >> K[i];
                            --L[i];
                            --R[i];
                            ad[L[i]].push_back({i, K[i]});
                            ad[R[i] + 1].push_back({i, -K[i]});
                    }
                    else if (t[i] == 2) {
                            cin >> L[i] >> R[i] >> K[i];
                            --L[i];
                            --R[i];
                            del[L[i]].push_back({i, K[i]});
                            del[R[i] + 1].push_back({i, -K[i]});
                    }
                    else {
                            cin >> A[i] >> B[i];
                            A[i]--;
                            GET[A[i]].push_back({B[i], i});
                    }
            }
            FOR(i, 0, n) {
                    for (auto [i, K]: del[i]) {
                            all.add(i, -K);
                            add(1, 0, q, i, q, -K);
                    }
                    for (auto [i, K]: ad[i]) {
                            pos.add(i, K);
                            all.add(i, K);
                            add(1, 0, q, i, q, K);
                    }
                    for (auto P: GET[i]) {
                            ll b = P[0];
                            int i = P[1];
                            ll all_pos = pos.get(i), mn = get(1, 0, q, 0, i + 1), sz = all.get(i) - (mn < 0 ? mn : 0);
                            b += all_pos - sz;
                            ans[i] = (b <= all_pos ? pos.find(b) : N);
                    }
            }
            FOR(i, 0, q) if (t[i] == 3)
                   cout << (ans[i] == N ? 0 : C[ans[i]]) << '\n'; 
    }
    //06:22:05

Compilation message (stderr)

foodcourt.cpp: In function 'void add(int, int, int, int, int, int)':
foodcourt.cpp:47:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |             int m = l + r >> 1;
      |                     ~~^~~
foodcourt.cpp: In function 'll get(int, int, int, int, int)':
foodcourt.cpp:60:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |             int m = l + r >> 1;
      |                     ~~^~~

• 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