Submission #794936

#	Time	Username	Problem	Language	Result	Execution time	Memory
794936		RushB	Food Court (JOI21_foodcourt)	C++17	100 / 100	381 ms	56328 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:19: 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:19: 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