Submission #1104625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104625		pit4h	Distributing Candies (IOI21_candies)	C++17	3 / 100	5123 ms	688184 KiB

candies

#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 = 5, 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 (stderr)

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;}
      |                   ^~~~

• Subtask 1: 3 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33