Submission #626652

#TimeUsernameProblemLanguageResultExecution timeMemory
626652tabrDistributing Candies (IOI21_candies)C++17
100 / 100
1311 ms33440 KiB
#include <bits/stdc++.h> using namespace std; #ifdef tabr #include "library/debug.cpp" #else #define debug(...) #endif // editorial struct segtree { using T = pair<long long, long long>; using F = long long; T e() { return make_pair((long long) 1e18, (long long) -1e18); } F id() { return 0; } T op(T a, T b) { a.first = min(a.first, b.first); a.second = max(a.second, b.second); return a; } T mapping(F f, T x) { x.first += f; x.second += f; return x; } F composition(F f, F g) { return f + g; } int n; int size; int log_size; vector<T> node; vector<F> lazy; segtree() : segtree(0) {} segtree(int _n) { build(vector<T>(_n, e())); } segtree(const vector<T>& v) { build(v); } void build(const vector<T>& v) { n = (int) v.size(); if (n <= 1) { log_size = 0; } else { log_size = 32 - __builtin_clz(n - 1); } size = 1 << log_size; node.resize(2 * size, e()); lazy.resize(size, id()); for (int i = 0; i < n; i++) { node[i + size] = v[i]; } for (int i = size - 1; i > 0; i--) { pull(i); } } void push(int x) { node[2 * x] = mapping(lazy[x], node[2 * x]); node[2 * x + 1] = mapping(lazy[x], node[2 * x + 1]); if (2 * x < size) { lazy[2 * x] = composition(lazy[x], lazy[2 * x]); lazy[2 * x + 1] = composition(lazy[x], lazy[2 * x + 1]); } lazy[x] = id(); } void pull(int x) { node[x] = op(node[2 * x], node[2 * x + 1]); } void set(int p, T v) { assert(0 <= p && p < n); p += size; for (int i = log_size; i >= 1; i--) { push(p >> i); } node[p] = v; for (int i = 1; i <= log_size; i++) { pull(p >> i); } } T get(int p) { assert(0 <= p && p < n); p += size; for (int i = log_size; i >= 1; i--) { push(p >> i); } return node[p]; } T get(int l, int r) { assert(0 <= l && l <= r && r <= n); l += size; r += size; for (int i = log_size; i >= 1; i--) { if (((l >> i) << i) != l) { push(l >> i); } if (((r >> i) << i) != r) { push((r - 1) >> i); } } T vl = e(); T vr = e(); while (l < r) { if (l & 1) { vl = op(vl, node[l++]); } if (r & 1) { vr = op(node[--r], vr); } l >>= 1; r >>= 1; } return op(vl, vr); } void apply(int p, F f) { assert(0 <= p && p < n); p += size; for (int i = log_size; i >= 1; i--) { push(p >> i); } node[p] = mapping(f, node[p]); for (int i = 1; i <= log_size; i++) { pull(p >> i); } } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= n); l += size; r += size; for (int i = log_size; i >= 1; i--) { if (((l >> i) << i) != l) { push(l >> i); } if (((r >> i) << i) != r) { push((r - 1) >> i); } } int ll = l; int rr = r; while (l < r) { if (l & 1) { node[l] = mapping(f, node[l]); if (l < size) { lazy[l] = composition(f, lazy[l]); } l++; } if (r & 1) { r--; node[r] = mapping(f, node[r]); if (l < size) { lazy[r] = composition(f, lazy[r]); } } l >>= 1; r >>= 1; } l = ll; r = rr; for (int i = 1; i <= log_size; i++) { if (((l >> i) << i) != l) { pull(l >> i); } if (((r >> i) << i) != r) { pull((r - 1) >> i); } } } }; vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) { int n = (int) c.size(); int q = (int) v.size(); segtree seg(vector<pair<long long, long long>>(q + 1, make_pair(0LL, 0LL))); vector<vector<int>> events(n + 1); for (int i = 0; i < q; i++) { events[l[i]].emplace_back(i); events[r[i] + 1].emplace_back(i); } vector<int> res(n); for (int i = 0; i < n; i++) { for (int j : events[i]) { if (l[j] == i) { seg.apply(j + 1, q + 1, v[j]); } else { seg.apply(j + 1, q + 1, -v[j]); } } auto last = seg.get(q).first; int low = -1; int high = q; while (high - low > 1) { int mid = (high + low) >> 1; auto p = seg.get(mid, q); if (p.second - p.first <= c[i]) { high = mid; } else { low = mid; } } debug(low, seg.node[1]); if (low == -1) { res[i] = (int) (last - seg.node[1].first); } else { auto p = seg.get(low, q); auto now = seg.get(low).first; if (p.second == now) { res[i] = (int) (last - p.first); } else if (p.first == now) { res[i] = (int) (c[i] + last - p.second); } else { assert(false); } } res[i] = min(c[i], max(0, res[i])); } return res; } #ifdef tabr int main() { ios::sync_with_stdio(false); cin.tie(0); debug(distribute_candies({10, 15, 13}, {0, 0}, {2, 1}, {20, -11})); debug(distribute_candies({10}, {0, 0}, {0, 0}, {-3, 12})); return 0; } #endif
#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...