Submission #933764

#TimeUsernameProblemLanguageResultExecution timeMemory
933764PanndaFood Court (JOI21_foodcourt)C++17
24 / 100
87 ms35136 KiB
#include <bits/stdc++.h> using namespace std; struct SegmentTree { int n; vector<long long> a, b; SegmentTree(int n) : n(n), a(4 * n, 0), b(4 * n, 0) {} void apply(int idx, long long x, long long y) { b[idx] = max(b[idx] + x, y); a[idx] = a[idx] + x; } void down(int idx) { apply(2 * idx + 1, a[idx], b[idx]); apply(2 * idx + 2, a[idx], b[idx]); a[idx] = b[idx] = 0; } void add(int ql, int qr, long long x, long long y) { auto dfs = [&](auto self, int idx, int l, int r) { if (r <= ql || qr <= l) return; if (ql <= l && r <= qr) return apply(idx, x, y); down(idx); int m = (l + r) >> 1; self(self, 2 * idx + 1, l, m); self(self, 2 * idx + 2, m, r); }; dfs(dfs, 0, 0, n); } long long get(int pos) { int idx = 0, l = 0, r = n; while (l + 1 < r) { down(idx); int m = (l + r) >> 1; if (pos < m) { idx = 2 * idx + 1; r = m; } else { idx = 2 * idx + 2; l = m; } } return max(a[idx], b[idx]); } }; struct Fenwick { int n; vector<long long> bit; Fenwick(int n) : n(n), bit(n + 1, 0) {} void add(int i, long long delta) { for (i++; i <= n; i += i & -i) { bit[i] += delta; } } void add(int ql, int qr, long long delta) { add(ql, +delta); add(qr, -delta); } long long get(int i) { long long res = 0; for (i++; i > 0; i -= i & -i) { res += bit[i]; } return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin >> n >> m >> q; vector<int> type(q), l(q), r(q), c(q), k(q), a(q), b(q); for (int i = 0; i < q; i++) { cin >> type[i]; if (type[i] == 1) { cin >> l[i] >> r[i] >> c[i] >> k[i]; l[i]--; } if (type[i] == 2) { cin >> l[i] >> r[i] >> k[i]; l[i]--; } if (type[i] == 3) { cin >> a[i] >> b[i]; a[i]--; b[i]--; } } SegmentTree seg(n); Fenwick fen(n); vector<vector<int>> inbox(q + 1); for (int i = 0; i < q; i++) { if (type[i] == 1) { seg.add(l[i], r[i], k[i], 0); fen.add(l[i], r[i], k[i]); } if (type[i] == 2) { seg.add(l[i], r[i], -k[i], 0); } if (type[i] == 3) { long long seg_get = seg.get(a[i]); long long fen_get = fen.get(a[i]); b[i] = fen_get - seg_get + b[i]; l[i] = 0, r[i] = q - 1; inbox[(l[i] + r[i]) >> 1].push_back(i); } } const int LOG = 18; for (int ite = 0; ite < LOG; ite++) { Fenwick fen(n); vector<vector<int>> new_inbox(q + 1); for (int m = 0; m < q; m++) { if (type[m] == 1) { fen.add(l[m], r[m], k[m]); } for (int i : inbox[m]) { if (b[i] < fen.get(a[i])) { r[i] = m; } else { l[i] = m + 1; } new_inbox[(l[i] + r[i]) >> 1].push_back(i); } } inbox = new_inbox; } for (int i = 0; i < q; i++) { if (type[i] == 3) { if (l[i] > i) { cout << 0 << '\n'; } else { cout << c[l[i]] << '\n'; } } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...