Submission #794913

#	Time	Username	Problem	Language	Result	Execution time	Memory
794913		RushB	Food Court (JOI21_foodcourt)	C++17	68 / 100	1075 ms	76400 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
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 = 3e5;
const int LG = 20;
long long B[N], K[N], mn[N << 2], delta[N << 2];
vector<int> V[4 * N], GET[N];
short t[N];
int L[N], R[N], C[N], A[N], n, m, q, ans[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_query(int v, int l, int r, int L, int R, int query_ind) {
        if (R <= l || r <= L) return;
        if (L <= l && r <= R) {
                V[v].push_back(query_ind);
                return;
        }
        int m = l + r >> 1;
        add_query(v << 1, l, m, L, R, query_ind);
        add_query(v << 1 | 1, m, r, L, R, query_ind);
}

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 (R <= l || r <= L) return INF;
        if (L <= l && r <= R) return mn[v];
        int m = l + r >> 1;
        return min(get(v << 1, l, m, L, R), get(v << 1 | 1, m, r, L, R)) + delta[v];
}

void solve(int v, int l, int r) {
        for (auto i: V[v]) {
                if (t[i] == 1) {
                        pos.add(i, K[i]);
                        all.add(i, K[i]);
                        add(1, 0, q, i, q, K[i]);
                }
                else {
                        all.add(i, -K[i]);
                        add(1, 0, q, i, q, -K[i]);
                }
        }
        if (l + 1 == r) {
                for (auto i: GET[l]) {
                        ll all_pos = pos.get(i), mn = get(1, 0, q, 0, i + 1), sz = all.get(i) - (mn < 0 ? mn : 0), b = B[i];
                        b += all_pos - sz;
                        ans[i] = (b <= all_pos ? pos.find(b) : N);
                }
        }
        else {
                int m = l + r >> 1;
                solve(v << 1, l, m);
                solve(v << 1 | 1, m, r);
        }
        for (auto i: V[v]) {
                if (t[i] == 1) {
                        pos.add(i, -K[i]);
                        all.add(i, -K[i]);
                        add(1, 0, q, i, q, -K[i]);
                }
                else {
                        all.add(i, +K[i]);
                        add(1, 0, q, i, q, +K[i]);
                }
        }
}

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]--;
                        add_query(1, 0, n, L[i], R[i], i);
                        R[i]--;
                }
                else if (t[i] == 2) {
                        cin >> L[i] >> R[i] >> K[i];
                        L[i]--;
                        add_query(1, 0, n, L[i], R[i], i);
                        R[i]--;
                }
                else {
                        cin >> A[i] >> B[i];
                        A[i]--;
                        GET[A[i]].push_back(i);
                }
        }
        solve(1, 0, 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_query(int, int, int, int, int, int)':
foodcourt.cpp:45:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |         int m = l + r >> 1;
      |                 ~~^~~
foodcourt.cpp: In function 'void add(int, int, int, int, int, int)':
foodcourt.cpp:56:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int m = l + r >> 1;
      |                 ~~^~~
foodcourt.cpp: In function 'll get(int, int, int, int, int)':
foodcourt.cpp:70:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |         int m = l + r >> 1;
      |                 ~~^~~
foodcourt.cpp: In function 'void solve(int, int, int)':
foodcourt.cpp:94:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |                 int m = l + r >> 1;
      |                         ~~^~~

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