#include "candies.h"
#include <vector>
#include <algorithm>
using namespace std;
long long tree_min[524288], tree_max[524288], lazy[524288];
void propagate(int i, int b, int e) {
if (!lazy[i]) return;
if (b != e) {
lazy[i * 2 + 1] += lazy[i];
lazy[i * 2 + 2] += lazy[i];
}
tree_min[i] += lazy[i];
tree_max[i] += lazy[i];
lazy[i] = 0;
}
long long query_min(int i, int b, int e, int l, int r) {
propagate(i, b, e);
if (r < l || r < b || e < l) return 4e18;
if (l <= b && e <= r) return tree_min[i];
int m = (b + e) / 2;
return min(query_min(i * 2 + 1, b, m, l, r), query_min(i * 2 + 2, m + 1, e, l, r));
}
long long query_max(int i, int b, int e, int l, int r) {
propagate(i, b, e);
if (r < l || r < b || e < l) return -4e18;
if (l <= b && e <= r) return tree_max[i];
int m = (b + e) / 2;
return max(query_max(i * 2 + 1, b, m, l, r), query_max(i * 2 + 2, m + 1, e, l, r));
}
void update(int i, int b, int e, int l, int r, long long v) {
propagate(i, b, e);
if (r < l || r < b || e < l) return;
if (l <= b && e <= r) {
lazy[i] += v;
propagate(i, b, e);
return;
}
int m = (b + e) / 2;
update(i * 2 + 1, b, m, l, r, v);
update(i * 2 + 2, m + 1, e, l, r, v);
tree_min[i] = min(tree_min[i * 2 + 1], tree_min[i * 2 + 2]);
tree_max[i] = max(tree_max[i * 2 + 1], tree_max[i * 2 + 2]);
}
vector<pair<int, int>> tag[200006];
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = c.size(), q = (int)l.size();
vector<int> s(n);
for (int i = 0; i < q; i++) {
tag[l[i]].push_back({ v[i], i });
tag[r[i] + 1].push_back({ -v[i], i });
}
for (int i = 0; i < n; i++) {
for (auto &j: tag[i]) update(0, 0, 262143, j.second + 1, 262143, j.first);
int l = 0, r = 262143;
while (l < r) {
int m = (l + r) / 2;
if (query_max(0, 0, 262143, m, 262143) - query_min(0, 0, 262143, m, 262143) < c[i]) r = m;
else l = m + 1;
}
if (!l) s[i] = query_min(0, 0, 262143, 262143, 262143) - query_min(0, 0, 262143, 0, 262143);
else if (query_min(0, 0, 262143, l - 1, l - 1) < query_min(0, 0, 262143, l, 262143)) s[i] = c[i] + query_min(0, 0, 262143, 262143, 262143) - query_max(0, 0, 262143, l, 262143);
else s[i] = query_min(0, 0, 262143, 262143, 262143) - query_min(0, 0, 262143, l, 262143);
}
return s;
}
