#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |