#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<int,int>;
using vi=vector<int>;
#define mp make_pair
#define eb emplace_back
#define x first
#define y second
#define sz(x)int((x).size())
#define all(x)(x).begin(),(x).end()
#define rep(i,a,b)for(int i=(a);i<(b);i++)
#define per(i,a,b)for(int i=(b)-1;i>=(a);i--)
bool ckmin(auto&a,auto b){return b<a?a=b,1:0;}
bool ckmax(auto&a,auto b){return b>a?a=b,1:0;}
#ifdef LOCAL
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.x<<", "<<p.y<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto&e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X);
#else
#define debug(...){}
#endif
const int MAXN = 2e5 + 5, MAXQ = 2e5 + 5, base = (1 << 19);
const ll INF = 1e18;
vi c, cnt;
int n, q;
vector<pair<ll, int>> tree[2 * base + 1];
void ins(int l, int r, pair<ll, int> val) {
l += base;
r += base;
tree[l].eb(val);
debug("tree", l, val);
if (l != r) {
tree[r].eb(val);
debug("tree", r, val);
}
while (l / 2 != r / 2) {
if (l % 2 == 0) {
tree[l+1].eb(val);
debug("tree", l+1, val);
}
if (r % 2 == 1) {
tree[r-1].eb(val);
debug("tree", r-1, val);
}
l /= 2;
r /= 2;
}
}
struct Solver {
ll pref[2*base], lazy[2*base], tree_min[2*base], tree_max[2*base];
ll total;
void init(int siz) {
total=0;
rep(i,0,2*base) {
pref[i] = lazy[i] = 0;
tree_min[i] = 0;
tree_max[i] = 0;
}
}
vector<vector<pair<int, vector<ll>>>> rollbacks;
void ins(int i, ll v) {
total += v;
rollbacks.eb(vector<pair<int,vector<ll>>>());
add(1, i, v);
}
ll get(ll cap) {
rollbacks.eb(vector<pair<int,vector<ll>>>());
auto [ceil, sub] = rec(cap);
debug(ceil, sub, total);
if (ceil == -1) {
return total - tree_min[1];
}
return total - sub + cap * ceil;
}
void undo(ll v) {
debug("undo", v);
total -= v;
assert(!rollbacks.empty());
vector<pair<int, vector<ll>>> vec = rollbacks.back();
reverse(all(vec));
for (auto& [id, values]: vec) {
assert(sz(values) == 4);
pref[id] = values[0];
lazy[id] = values[1];
tree_min[id] = values[2];
tree_max[id] = values[3];
}
rollbacks.pop_back();
}
void push(int id, ll v) {
rollbacks.back().eb(mp(id, vector<ll>({pref[id], lazy[id], tree_min[id], tree_max[id]})));
pref[id] += v;
lazy[id] += v;
tree_min[id] += v;
tree_max[id] += v;
}
void add(int id, int i, ll v, int rl=0, int rr=base-1) {
rollbacks.back().eb(mp(id, vector<ll>({pref[id], lazy[id], tree_min[id], tree_max[id]})));
if (rr < i) return;
if (rl >= i) {
push(id, v);
return;
}
push(id*2,lazy[id]);
push(id*2+1,lazy[id]);
lazy[id]=0;
int mid = (rl+rr)/2;
add(id*2,i,v,rl,mid);
add(id*2+1,i,v,mid+1,rr);
tree_min[id] = min(tree_min[id*2], tree_min[id*2+1]);
tree_max[id] = max(tree_max[id*2], tree_max[id*2+1]);
}
pair<int,ll> rec(ll cap, int id=1, int rl=0, int rr=base-1, ll suf_min=INF, ll suf_max=-INF) {
debug("rec", cap, id, rl, rr, suf_min, suf_max, tree_min[id], tree_max[id]);
rollbacks.back().eb(mp(id, vector<ll>({pref[id], lazy[id], tree_min[id], tree_max[id]})));
if (max(suf_max, tree_max[id]) - min(suf_min, tree_min[id]) < cap) {
return mp(-1,0LL);
}
if (rl == rr) {
if (suf_max - pref[id] >= cap) {
return mp(1,suf_max);
}
else {
assert(pref[id] - suf_min >= cap);
return mp(0,suf_min);
}
}
push(id*2,lazy[id]);
push(id*2+1,lazy[id]);
lazy[id]=0;
int mid=(rl+rr)/2;
pair<int,ll> res = rec(cap, id*2+1, mid+1, rr, suf_min, suf_max);
if (res != mp(-1,0LL)) {
return res;
}
ll new_min = min(suf_min, tree_min[id*2+1]), new_max = max(suf_max, tree_max[id*2+1]);
return rec(cap, id*2, rl, mid, new_min, new_max);
}
} solver;
void solve(int id, int l, int r) {
debug(id, l, r);
for (auto& [v, i]: tree[id]) {
debug("ins", i, v);
solver.ins(i, v);
}
if (l == r) {
if (l < n) {
cnt[l] = solver.get(c[l]);
solver.undo(0);
}
}
else {
int mid = (l+r)/2;
solve(id * 2, l, mid);
solve(id * 2 + 1, mid + 1, r);
}
vector<ll> to_undo;
for (auto& [v, i]: tree[id]) {
to_undo.eb(v);
}
reverse(all(to_undo));
for (ll v: to_undo) {
solver.undo(v);
}
}
vector<int> distribute_candies(vector<int> _c, vector<int> l,
vector<int> r, vector<int> v) {
c = _c;
n = c.size(); q = sz(l);
vector<int> s(n);
cnt.resize(n); rep(i,0,n) cnt[i] = 0;
rep(i,0,q) {
debug("INS", l[i], r[i], v[i], i);
ins(l[i], r[i], mp(v[i], i+1));
}
solver.init(q);
solve(1, 0, base - 1);
rep(i,0,n) s[i] = cnt[i];
return s;
}
Compilation message
candies.cpp:16:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
16 | bool ckmin(auto&a,auto b){return b<a?a=b,1:0;}
| ^~~~
candies.cpp:16:19: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
16 | bool ckmin(auto&a,auto b){return b<a?a=b,1:0;}
| ^~~~
candies.cpp:17:12: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
17 | bool ckmax(auto&a,auto b){return b>a?a=b,1:0;}
| ^~~~
candies.cpp:17:19: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
17 | bool ckmax(auto&a,auto b){return b>a?a=b,1:0;}
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
57936 KB |
Output is correct |
| 2 |
Correct |
15 ms |
57936 KB |
Output is correct |
| 3 |
Correct |
79 ms |
67492 KB |
Output is correct |
| 4 |
Correct |
139 ms |
66332 KB |
Output is correct |
| 5 |
Correct |
216 ms |
66828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5105 ms |
561668 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
57936 KB |
Output is correct |
| 2 |
Execution timed out |
5087 ms |
659160 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
57936 KB |
Output is correct |
| 2 |
Correct |
23 ms |
57936 KB |
Output is correct |
| 3 |
Execution timed out |
5178 ms |
1736652 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
57936 KB |
Output is correct |
| 2 |
Correct |
15 ms |
57936 KB |
Output is correct |
| 3 |
Correct |
79 ms |
67492 KB |
Output is correct |
| 4 |
Correct |
139 ms |
66332 KB |
Output is correct |
| 5 |
Correct |
216 ms |
66828 KB |
Output is correct |
| 6 |
Execution timed out |
5105 ms |
561668 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
