제출 #1243031

#제출 시각아이디문제언어결과실행 시간메모리
1243031nibert사탕 분배 (IOI21_candies)C++20
0 / 100
156 ms14508 KiB
#include <vector> #include <algorithm> using namespace std; struct SegmentTree { int n; vector<int> tree, lazy, cap; SegmentTree(const vector<int>& capacity) { n = capacity.size(); cap = capacity; tree.assign(4 * n, 0); lazy.assign(4 * n, 0); } void push(int node, int l, int r) { if (lazy[node] == 0) return; if (l == r) { tree[node] = min(cap[l], tree[node] + lazy[node]); } else { int mid = (l + r) / 2; // propagate lazily to children lazy[2*node] += lazy[node]; lazy[2*node+1] += lazy[node]; } lazy[node] = 0; } void update(int node, int l, int r, int ql, int qr, int val) { push(node, l, r); if (r < ql || l > qr) return; if (ql <= l && r <= qr) { lazy[node] += val; push(node, l, r); return; } int mid = (l + r) / 2; update(2*node, l, mid, ql, qr, val); update(2*node+1, mid+1, r, ql, qr, val); tree[node] = 0; // not needed unless we do queries } void get_final(int node, int l, int r, vector<int>& result) { push(node, l, r); if (l == r) { result[l] = tree[node]; return; } int mid = (l + r) / 2; get_final(2*node, l, mid, result); get_final(2*node+1, mid+1, r, result); } }; vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) { int n = c.size(), q = l.size(); SegmentTree seg(c); for (int i = 0; i < q; ++i) { seg.update(1, 0, n - 1, l[i], r[i], v[i]); } vector<int> result(n); seg.get_final(1, 0, n - 1, result); return result; }
#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...