Submission #467569

#	Time	Username	Problem	Language	Result	Execution time	Memory
467569		rainboy	Distributing Candies (IOI21_candies)	C++17	100 / 100	415 ms	26780 KiB

candies

#include "candies.h"
#include <vector>

using namespace std;

typedef vector<int> vi;

const int Q = 200000, N_ = 1 << 18;	/* N_ = pow2(ceil(log(Q))) */

long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int xx[Q * 2], hh[Q * 2];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (xx[hh[j]] == xx[h])
				j++;
			else if (xx[hh[j]] < xx[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

long long sum[N_ * 2], mn[N_ * 2], mx[N_ * 2]; int n_;

void pul(int i) {
	int l = i << 1, r = l | 1;

	sum[i] = sum[l] + sum[r];
	mn[i] = min(mn[r], mn[l] + sum[r]);
	mx[i] = max(mx[r], mx[l] + sum[r]);
}

void update(int i, int x) {
	i += n_;
	sum[i] = x, mn[i] = min(x, 0), mx[i] = max(x, 0);
	while (i > 1)
		pul(i >>= 1);
}

int query(int c) {
	int i;
	long long s, x, y;

	if (mx[1] - mn[1] <= c)
		return mx[1];
	i = 1, s = 0, x = 0, y = 0;
	while (i < n_) {
		long long s_ = sum[i << 1 | 1] + s, x_ = min(x, mn[i << 1 | 1] + s), y_ = max(y, mx[i << 1 | 1] + s);

		if (y_ - x_ <= c) {
			i = i << 1 | 0;
			s = s_, x = x_, y = y_;
		} else
			i = i << 1 | 1;
	}
	return min(max(sum[i] + s, y), c + x);
}

vi distribute_candies(vi cc, vi ll, vi rr, vi vv) {
	int n = cc.size(), q = ll.size(), h, i;
	vi aa(n);

	for (h = 0; h < q; h++)
		xx[h << 1 | 0] = ll[h], xx[h << 1 | 1] = rr[h] + 1;
	n_ = 1;
	while (n_ < q)
		n_ <<= 1;
	for (h = 0; h < q * 2; h++)
		hh[h] = h;
	sort(hh, 0, q * 2);
	for (i = 0, h = 0; i < n; i++) {
		while (h < q * 2 && xx[hh[h]] <= i)
			update(hh[h] >> 1, (hh[h] & 1) == 0 ? vv[hh[h] >> 1] : 0), h++;
		aa[i] = query(cc[i]);
	}
	return aa;
}

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