#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, MAGIC = 500;
const int BUCKET_SIZE = 500, BUCKETS = MAXN / BUCKET_SIZE + 1;
const ll INF = 1e18;
vi c, cnt;
vi buckets[BUCKETS];
int bucket_ord[BUCKETS][BUCKET_SIZE];
int n, q;
void bucket_add(int v, int id) {
debug("bucket_add", v, id);
buckets[id].eb(v);
}
int bucket_start(int id) { return id * BUCKET_SIZE; }
int bucket_end(int id) { return (id + 1) * BUCKET_SIZE; }
int bucket_size(int id) { return bucket_end(id) - bucket_start(id); }
int get_idx(int id, int i) { return bucket_start(id) + i; }
int BOTTOM(int i) { return 2 * i; }
int UP(int i) { return 2 * i + 1; }
int GET_ID(int i) { return i / 2; }
int f[2 * MAXN], fsz[2 * MAXN], frep[2 * MAXN];
int find(int x) {
if (f[x] != x) f[x] = find(f[x]);
return f[x];
}
void unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
if (fsz[x] < fsz[y]) swap(x, y);
fsz[x] += fsz[y];
f[y] = x;
ckmax(frep[x], frep[y]);
}
void f_clr(int m) {
rep(i,0,2*(m + 1)) {
f[i] = i;
fsz[i] = 1;
frep[i] = i;
}
}
void bucket_eval(int id) {
debug("eval", id, buckets[id]);
if (buckets[id].empty()) return;
int m = sz(buckets[id]);
f_clr(m);
pair<ll, int> min_suf = mp(INF, 2 * m), max_suf = mp(-INF, 2 * m);
vector<ll> suf(m + 1);
ll sum = 0;
vector<pair<ll, pi>> edges;
per(i,0,m) {
ckmin(min_suf, mp(sum, i));
ckmax(max_suf, mp(sum, i));
sum += buckets[id][i];
suf[i] = sum;
// sum - max_suf <= 0
if (max_suf.x >= sum) {
edges.eb(0LL, mp(BOTTOM(i), BOTTOM(max_suf.y + 1)));
}
// sum - min_suf >= c
edges.eb(sum - min_suf.x, mp(BOTTOM(i), UP(min_suf.y + 1)));
// sum - min_suf >= 0
if (min_suf.x <= sum) {
edges.eb(0LL, mp(UP(i), UP(min_suf.y + 1)));
}
// sum - max_suf <= -c
edges.eb(max_suf.x - sum, mp(UP(i), BOTTOM(max_suf.y + 1)));
}
sort(all(edges));
reverse(all(edges));
debug(edges);
vector<bool> del(2 * (m + 1));
int j = 0;
rep(i,0,bucket_size(id)) {
int cur = bucket_ord[id][i];
debug(i, cur);
while (j < sz(edges) && edges[j].x >= c[cur]) {
debug(edges[j].y);
if (!del[edges[j].y.x]) {
del[edges[j].y.x] = 1;
unite(edges[j].y.x, edges[j].y.y);
}
j++;
}
// step 1. go until reaching 0 or c[idx]
int x = 0, node = -1;
if ((ll)cnt[cur] + (suf[0] - max_suf.x) <= 0LL) {
x = max_suf.y + 1;
node = BOTTOM(x);
}
else if ((ll)cnt[cur] + (suf[0] - min_suf.x) >= (ll)c[cur]) {
x = min_suf.y + 1;
node = UP(x);
}
debug(x, node);
// step 2. jump to final point reaching 0 or c[idx]
if (node == BOTTOM(x) || node == UP(x)) {
node = frep[find(node)];
x = GET_ID(node);
}
debug(x, node);
// step 3. calculate final value knowing no overflow happens
if (node == BOTTOM(x)) {
cnt[cur] = suf[x];
}
else if (node == UP(x)) {
cnt[cur] = c[cur] + suf[x];
}
else {
cnt[cur] += suf[x];
}
}
buckets[id].clear();
}
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;
vi tmp_cnt(n / BUCKET_SIZE + 1, 0);
vector<pi> vec;
rep(i,0,n) vec.eb(c[i], i);
sort(all(vec));
reverse(all(vec));
for (auto [_, i]: vec) {
bucket_ord[i / BUCKET_SIZE][tmp_cnt[i / BUCKET_SIZE]++] = i;
}
rep(i,0,q) {
int left_bucket = l[i] / BUCKET_SIZE, right_bucket = r[i] / BUCKET_SIZE;
rep(j,left_bucket+1,right_bucket) {
bucket_add(v[i], j);
}
bucket_eval(left_bucket);
debug("rep", l[i], min(r[i]+1,(left_bucket+1)*BUCKET_SIZE));
rep(j,l[i],min(r[i] + 1, bucket_start(left_bucket+1))) {
cnt[j] += v[i];
cnt[j] = max(0, min(c[j], cnt[j]));
}
if (left_bucket != right_bucket) {
bucket_eval(right_bucket);
debug("rep", (right_bucket-1)*BUCKET_SIZE+1, r[i] + 1);
rep(j,bucket_start(right_bucket), r[i] + 1) {
cnt[j] += v[i];
cnt[j] = max(0, min(c[j], cnt[j]));
}
}
debug(cnt);
}
rep(id,0,(n-1) / BUCKET_SIZE + 1) {
bucket_eval(id);
}
s = cnt;
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 |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
5 ms |
4856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4476 ms |
17972 KB |
Output is correct |
| 2 |
Correct |
4819 ms |
21556 KB |
Output is correct |
| 3 |
Correct |
4875 ms |
21432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
234 ms |
11000 KB |
Output is correct |
| 3 |
Correct |
103 ms |
11828 KB |
Output is correct |
| 4 |
Execution timed out |
5054 ms |
17544 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
384 ms |
45840 KB |
Output is correct |
| 4 |
Correct |
226 ms |
16060 KB |
Output is correct |
| 5 |
Execution timed out |
5099 ms |
414708 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
336 KB |
Output is correct |
| 5 |
Correct |
5 ms |
4856 KB |
Output is correct |
| 6 |
Correct |
4476 ms |
17972 KB |
Output is correct |
| 7 |
Correct |
4819 ms |
21556 KB |
Output is correct |
| 8 |
Correct |
4875 ms |
21432 KB |
Output is correct |
| 9 |
Correct |
1 ms |
336 KB |
Output is correct |
| 10 |
Correct |
234 ms |
11000 KB |
Output is correct |
| 11 |
Correct |
103 ms |
11828 KB |
Output is correct |
| 12 |
Execution timed out |
5054 ms |
17544 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
