oj.uz

답안 #1104641

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1104641 2024-10-24T08:02:07 Z pit4h 사탕 분배 (IOI21_candies) C++17
38 / 100
 5000 ms 250824 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 = 900, 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 576 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 4 ms 4688 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3799 ms 16492 KB Output is correct
2 Correct 3634 ms 16564 KB Output is correct
3 Correct 3749 ms 16568 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 207 ms 9204 KB Output is correct
3 Correct 82 ms 11448 KB Output is correct
4 Correct 3557 ms 16628 KB Output is correct
5 Correct 3669 ms 16556 KB Output is correct
6 Correct 4106 ms 16608 KB Output is correct
7 Correct 4094 ms 16580 KB Output is correct

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 360 ms 30840 KB Output is correct
4 Correct 161 ms 13240 KB Output is correct
5 Execution timed out 5091 ms 250824 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 576 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 4 ms 4688 KB Output is correct
6 Correct 3799 ms 16492 KB Output is correct
7 Correct 3634 ms 16564 KB Output is correct
8 Correct 3749 ms 16568 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 207 ms 9204 KB Output is correct
11 Correct 82 ms 11448 KB Output is correct
12 Correct 3557 ms 16628 KB Output is correct
13 Correct 3669 ms 16556 KB Output is correct
14 Correct 4106 ms 16608 KB Output is correct
15 Correct 4094 ms 16580 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 360 ms 30840 KB Output is correct
19 Correct 161 ms 13240 KB Output is correct
20 Execution timed out 5091 ms 250824 KB Time limit exceeded
21 Halted 0 ms 0 KB -