#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "candies.h"
const int MAX_N = 200010;
const ll inf = 1ll << 59;
int n, m;
struct node {
ll mx, mn, at;
void operator += (ll v) { mx += v, mn += v, at += v; }
node (ll a, ll b) : mx(a), mn(b), at(0) {}
node (ll v) : at(0), mx(v), mn(v) {}
node (node a, node b) : at(0), mx(max(a.mx, b.mx)), mn(min(a.mn, b.mn)) {}
node () : mx(0), mn(0), at(0) {}
bool valid(int c) { return mx - mn <= c; }
};
vector<pair<ll,ll>> op[MAX_N];
struct sgt {
int n;
vector<node> val;
sgt(int n) : n(n) {
val.resize(n<<1);
}
void push(int i) {
if (i >= n) return;
val[i<<1] += val[i].at;
val[i<<1|1] += val[i].at;
val[i].at = 0;
}
void upd(int i) {
if (i >= n) return;
push(i);
val[i] = node(val[i<<1], val[i<<1|1]);
}
void add(int l, int r, ll v) {
l += n, r += n;
int sl = l, sr = r;
for (;l < r;l>>=1, r>>=1) {
if (l&1) val[l++] += v;
if (r&1) val[--r] += v;
}
for (;sl>>=1, sr>>=1;)
upd(sl), upd(sr);
}
node qry(int l, int r) {
l += n, r += n;
for (int i = 18;i > 0;--i) push(l>>i), push(r>>i);
node ret(-inf, inf);
for (;l < r;l>>=1, r>>=1) {
if (l&1) ret = node(ret, val[l++]);
if (r&1) ret = node(ret, val[--r]);
}
return ret;
}
}tree(0);
int qry(int c) {
auto s0 = tree.qry(0, m);
ll all = tree.qry(m-1, m), mx;
if (s0.mx - s0.mn <= c) {
return all - s0.mn;
}
int l = 0, r = m-1, mid;
while (l < r) {
mid = l + r >> 1;
if (tree.qry(mid, m).valid(c))
r = mid;
else
l = mid+1;
}
assert(l > 0);
ll v = tree.qry(l-1, l).mx;
auto sl = tree.qry(l, m);
if (sl.mx > v + c) {
return c + (all - sl.mx);
}
else return all - sl.mn;
}
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
n = c.size(), m = l.size();
for (int i = 0;i < m;++i) {
op[l[i]].pb(i+1, v[i]);
op[r[i]+1].pb(i+1, -v[i]);
}
++m;
tree = sgt(m);
vector<int> res(n);
for (int i = 0;i < n;++i) {
for (auto [j, w] : op[i])
tree.add(j, m, w);
res[i] = qry(c[i]);
}
return res;
}
Compilation message
candies.cpp: In constructor 'node::node(ll)':
candies.cpp:24:13: warning: 'node::at' will be initialized after [-Wreorder]
24 | ll mx, mn, at;
| ^~
candies.cpp:24:5: warning: 'll node::mx' [-Wreorder]
24 | ll mx, mn, at;
| ^~
candies.cpp:27:2: warning: when initialized here [-Wreorder]
27 | node (ll v) : at(0), mx(v), mn(v) {}
| ^~~~
candies.cpp: In constructor 'node::node(node, node)':
candies.cpp:24:13: warning: 'node::at' will be initialized after [-Wreorder]
24 | ll mx, mn, at;
| ^~
candies.cpp:24:5: warning: 'll node::mx' [-Wreorder]
24 | ll mx, mn, at;
| ^~
candies.cpp:28:2: warning: when initialized here [-Wreorder]
28 | node (node a, node b) : at(0), mx(max(a.mx, b.mx)), mn(min(a.mn, b.mn)) {}
| ^~~~
candies.cpp: In function 'int qry(int)':
candies.cpp:76:19: error: cannot convert 'node' to 'll' {aka 'long long int'} in initialization
76 | ll all = tree.qry(m-1, m), mx;
| ~~~~~~~~^~~~~~~~
| |
| node
candies.cpp:82:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
82 | mid = l + r >> 1;
| ~~^~~
candies.cpp:76:29: warning: unused variable 'mx' [-Wunused-variable]
76 | ll all = tree.qry(m-1, m), mx;
| ^~
