oj.uz

Submission #1104631

# Submission time Handle Problem Language Result Execution time Memory
1104631 2024-10-24T07:51:33 Z pit4h Distributing Candies (IOI21_candies) C++17
38 / 100
 5000 ms 167808 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 = 1500, 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 472 KB Output is correct
5 Correct 5 ms 336 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4025 ms 16296 KB Output is correct
2 Correct 3837 ms 16316 KB Output is correct
3 Correct 4006 ms 16312 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 187 ms 5104 KB Output is correct
3 Correct 84 ms 11332 KB Output is correct
4 Correct 3473 ms 16316 KB Output is correct
5 Correct 3334 ms 16312 KB Output is correct
6 Correct 4097 ms 16284 KB Output is correct
7 Correct 3983 ms 16316 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 466 ms 5104 KB Output is correct
4 Correct 118 ms 12728 KB Output is correct
5 Execution timed out 5063 ms 167808 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 472 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 4025 ms 16296 KB Output is correct
7 Correct 3837 ms 16316 KB Output is correct
8 Correct 4006 ms 16312 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 187 ms 5104 KB Output is correct
11 Correct 84 ms 11332 KB Output is correct
12 Correct 3473 ms 16316 KB Output is correct
13 Correct 3334 ms 16312 KB Output is correct
14 Correct 4097 ms 16284 KB Output is correct
15 Correct 3983 ms 16316 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 466 ms 5104 KB Output is correct
19 Correct 118 ms 12728 KB Output is correct
20 Execution timed out 5063 ms 167808 KB Time limit exceeded
21 Halted 0 ms 0 KB -