oj.uz

Submission #1104637

# Submission time Handle Problem Language Result Execution time Memory
1104637 2024-10-24T07:58:05 Z pit4h Distributing Candies (IOI21_candies) C++17
38 / 100
 5000 ms 307076 KB 
#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 = 700, 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;}
      |                   ^~~~

Subtask #1
3.0 / 3.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 384 KB Output is correct
5 Correct 4 ms 4688 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4041 ms 16872 KB Output is correct
2 Correct 3963 ms 16824 KB Output is correct
3 Correct 4190 ms 16824 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 215 ms 9344 KB Output is correct
3 Correct 82 ms 11708 KB Output is correct
4 Correct 4105 ms 16752 KB Output is correct
5 Correct 4240 ms 17224 KB Output is correct
6 Correct 4547 ms 16912 KB Output is correct
7 Correct 4665 ms 16896 KB Output is correct

Subtask #4
0 / 29.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 387 ms 30868 KB Output is correct
4 Correct 176 ms 13756 KB Output is correct
5 Execution timed out 5067 ms 307076 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.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 384 KB Output is correct
5 Correct 4 ms 4688 KB Output is correct
6 Correct 4041 ms 16872 KB Output is correct
7 Correct 3963 ms 16824 KB Output is correct
8 Correct 4190 ms 16824 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 215 ms 9344 KB Output is correct
11 Correct 82 ms 11708 KB Output is correct
12 Correct 4105 ms 16752 KB Output is correct
13 Correct 4240 ms 17224 KB Output is correct
14 Correct 4547 ms 16912 KB Output is correct
15 Correct 4665 ms 16896 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 387 ms 30868 KB Output is correct
19 Correct 176 ms 13756 KB Output is correct
20 Execution timed out 5067 ms 307076 KB Time limit exceeded
21 Halted 0 ms 0 KB -