제출 #794921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
794921		RushB	푸드 코트 (JOI21_foodcourt)	C++17	68 / 100	1096 ms	117420 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 = 18;
long long B[N], mn[N << 2], delta[N << 2];
vector<array<int, 2>> ad[N << 2], del[N << 2];
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_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) {
                if (t[query_ind] == 1)
                        ad[v].push_back({query_ind, K[query_ind]});
                else
                        del[v].push_back({query_ind, K[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 (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];
}

void solve(int v, int l, int r) {
        for (auto [i, K]: ad[v]) {
                pos.add(i, K);
                all.add(i, K);
                add(1, 0, q, i, q, K);
        }
        for (auto [i, K]: del[v]) {
                all.add(i, -K);
                add(1, 0, q, i, q, -K);
        }
        if (l + 1 == r) {
                for (auto P: GET[l]) {
                        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);
                }
        }
        else {
                int m = l + r >> 1;
                solve(v << 1, l, m);
                solve(v << 1 | 1, m, r);
        }
        for (auto [i, K]: ad[v]) {
                pos.add(i, -K);
                all.add(i, -K);
                add(1, 0, q, i, q, -K);
        }
        for (auto [i, K]: del[v]) {
                all.add(i, K);
                add(1, 0, q, i, q, K);
        }
}

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({B[i], 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

컴파일 시 표준 에러 (stderr) 메시지

foodcourt.cpp: In function 'void add_query(int, int, int, int, int, int)':
foodcourt.cpp:49:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         int m = l + r >> 1;
      |                 ~~^~~
foodcourt.cpp: In function 'void add(int, int, int, int, int, int)':
foodcourt.cpp:60:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         int m = l + r >> 1;
      |                 ~~^~~
foodcourt.cpp: In function 'll get(int, int, int, int, int)':
foodcourt.cpp:73:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |         int m = l + r >> 1;
      |                 ~~^~~
foodcourt.cpp: In function 'void solve(int, int, int)':
foodcourt.cpp:102:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |                 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