oj.uz

답안 #1104630

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1104630 2024-10-24T07:50:22 Z pit4h 사탕 분배 (IOI21_candies) C++17
38 / 100
 5000 ms 229064 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 = 1000, 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 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 3 ms 592 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3859 ms 16520 KB Output is correct
2 Correct 3759 ms 16508 KB Output is correct
3 Correct 3691 ms 16616 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 182 ms 5240 KB Output is correct
3 Correct 76 ms 11456 KB Output is correct
4 Correct 3511 ms 16508 KB Output is correct
5 Correct 3621 ms 16520 KB Output is correct
6 Correct 4138 ms 16484 KB Output is correct
7 Correct 3971 ms 16516 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 463 ms 5192 KB Output is correct
4 Correct 146 ms 13240 KB Output is correct
5 Execution timed out 5076 ms 229064 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 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 3 ms 592 KB Output is correct
6 Correct 3859 ms 16520 KB Output is correct
7 Correct 3759 ms 16508 KB Output is correct
8 Correct 3691 ms 16616 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 182 ms 5240 KB Output is correct
11 Correct 76 ms 11456 KB Output is correct
12 Correct 3511 ms 16508 KB Output is correct
13 Correct 3621 ms 16520 KB Output is correct
14 Correct 4138 ms 16484 KB Output is correct
15 Correct 3971 ms 16516 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 463 ms 5192 KB Output is correct
19 Correct 146 ms 13240 KB Output is correct
20 Execution timed out 5076 ms 229064 KB Time limit exceeded
21 Halted 0 ms 0 KB -