#include <bits/stdc++.h>
#ifdef ONPC
#include "t_debug.cpp"
#else
#define debug(...) 42
#endif
using namespace std;
//namespace pbds = __gnu_pbds;
using ll = long long;
const int inf = 1e9;
const ll infl = 1e18;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(RANDOM);
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p) { return is >> p.first >> p.second; }
template<typename Cont> int sz(const Cont& cont) { return int(cont.size()); }
const string fileio = "";
constexpr int tests = 1, nmax = 2e5, nlog = __lg(nmax), mod = 1e9+7;
#define int ll
struct segtree {
struct node{
ll sum=0;
ll mnp=0, mxp=0;
static node single(int x) {
return {x, min((int)0, x), max((int)0, x)};
}
node operator+(const node& rhs) {
return node{
sum + rhs.sum,
min(mnp, sum + rhs.mnp),
max(mxp, sum + rhs.mxp),
};
}
};
int n;
vector<node> t;
segtree(int m) : n(m), t(m*4) {}
void update(int i, int x) {
t[i += n] = node::single(x);
for (i /= 2; i >= 1; i /= 2)
t[i] = t[i*2] + t[i*2+1];
}
node query(int l, int r) {
l += n;
r += n;
node nl, nr;
while (l <= r) {
if (l%2==1) nl = nl + t[l++];
if (r%2==0) nr = t[r--] + nr;
l /= 2;
r /= 2;
}
return nl + nr;
}
};
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
int n = sz(c), q = sz(l);
vector<int> res(n), real(n + 1);
for (int i = 0; i < q; i++) {
real[l[i]] += v[i];
real[r[i]+1] -= v[i];
}
for (int i = 1; i < n; i++)
real[i] += real[i-1];
reverse(l.begin(), l.end());
reverse(r.begin(), r.end());
reverse(v.begin(), v.end());
segtree st(q);
for (int j = 0; j < q; j++)
st.update(j, -v[j]);
for (int i = 0; i < n; i++) {
int cur = 0, low = 0, high = 0;
int lb = -1, rb = q-1;
auto check = [&](int j) {
auto node = st.query(0, j);
cur = node.sum;
low = node.mnp;
high = node.mxp;
if (high - low >= c[i]) {
if (cur == high)
res[i] = -low;
else
res[i] = c[i] - high;
return true;
}
return false;
};
while (lb < rb-1) {
int mid = (lb + rb) / 2;
if (check(mid))
rb = mid;
else lb = mid;
}
if (!check(rb)) {
res[i] = -low;
}
}
return res;
}
/*
█████ █████ ███ ████
▒▒███ ▒▒███ ▒▒▒ ▒▒███
███████ ████████ ███████ ████ ▒███ █████ ████ ██████ ████████
███▒▒███ ▒▒███▒▒███ ███▒▒███ ▒▒███ ▒███ ▒▒███ ▒███ ███▒▒███▒▒███▒▒███
▒███ ▒███ ▒███ ▒▒▒ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒▒▒
▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███
▒▒████████ █████ ▒▒████████ █████ █████ ▒▒███████ ▒▒██████ █████
▒▒▒▒▒▒▒▒ ▒▒▒▒▒ ▒▒▒▒▒▒▒▒ ▒▒▒▒▒ ▒▒▒▒▒ ▒▒▒▒▒███ ▒▒▒▒▒▒ ▒▒▒▒▒
███ ▒███
▒▒██████
▒▒▒▒▒▒
*/
Compilation message
/usr/bin/ld: /tmp/ccShGILN.o: in function `main':
grader.cpp:(.text.startup+0x30e): undefined reference to `distribute_candies(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
