Submission #1067267

#TimeUsernameProblemLanguageResultExecution timeMemory
1067267ZicrusDistributing Candies (IOI21_candies)C++17
0 / 100
184 ms24660 KiB
#include <bits/stdc++.h> #include "candies.h" using namespace std; typedef long long ll; struct node { ll offset; ll mn, mx; }; ll n, q, cap; ll pow2; vector<node> seg; void propagate(ll i) { seg[2*i].offset += seg[i].offset; seg[2*i].mn = clamp(seg[2*i].mn + seg[i].offset, seg[i].mn, seg[i].mx); seg[2*i].mx = clamp(seg[2*i].mx + seg[i].offset, seg[i].mn, seg[i].mx); seg[2*i+1].offset += seg[i].offset; seg[2*i+1].mn = clamp(seg[2*i+1].mn + seg[i].offset, seg[i].mn, seg[i].mx); seg[2*i+1].mx = clamp(seg[2*i+1].mx + seg[i].offset, seg[i].mn, seg[i].mx); } void propagateRecursive(ll i = 1) { if (i >= pow2) return; propagate(i); propagateRecursive(2*i); propagateRecursive(2*i+1); } void update(ll low, ll high, ll val, ll nl = 0, ll nh = pow2-1, ll i = 1) { if (high < nl || low > nh) return; if (low <= nl && high >= nh) { seg[i].offset += val; seg[i].mn = clamp(seg[i].mn + val, 0ll, cap); seg[i].mx = clamp(seg[i].mx + val, 0ll, cap); return; } if (i >= pow2) return; propagate(i); update(low, high, val, nl, (nl+nh)/2, 2*i); update(low, high, val, (nl+nh)/2+1, nh, 2*i+1); } vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) { n = c.size(); q = v.size(); cap = c[0]; pow2 = 1ll << (ll)ceil(log2(n)); seg = vector<node>(2*pow2, {0, 0, cap}); for (int i = 0; i < q; i++) { update(l[i], r[i], v[i]); } propagateRecursive(); vector<int> res(n); for (int i = 0; i < n; i++) { node &e = seg[pow2+i]; res[i] = clamp(e.offset, e.mn, e.mx); } return res; }
#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...