Submission #403976

#	Time	Username	Problem	Language	Result	Execution time	Memory
403976		rainboy	Dancing Elephants (IOI11_elephants)	C11	100 / 100	7810 ms	12684 KiB

elephants

/* upsolve after reading solution */
#include "elephants.h"
#include <string.h>

#define N	150000
#define K	1000
#define	M	150
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

unsigned int X = 12345;

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

int xx[N], ii[N], hh[N], n, d;

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

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

int iii[M][K * 2], cnt[M][K * 2], xx_[M][K * 2], kk[M], m;

void build(int h) {
	int i, j;

	for (i = kk[h] - 1, j = kk[h]; i >= 0; i--) {
		int x = xx[iii[h][i]];

		while (xx[iii[h][j - 1]] - x > d)
			j--;
		if (j == kk[h])
			cnt[h][i] = 1, xx_[h][i] = x;
		else
			cnt[h][i] = cnt[h][j] + 1, xx_[h][i] = xx_[h][j];
	}
}

void build_() {
	int h, i;

	for (h = 0; h < m; h++) {
		int l = h * K, r = min((h + 1) * K, n);

		kk[h] = r - l;
		for (i = l; i < r; i++)
			iii[h][i - l] = ii[i], hh[ii[i]] = h;
		build(h);
	}
}

void extract() {
	int h, h_, i;

	for (h = 0, h_ = 0; h < m; h++)
		for (i = 0; i < kk[h]; i++)
			ii[h_++] = iii[h][i];
}

void init(int n_, int d_, int *xx_) {
	int i;

	n = n_, d = d_, memcpy(xx, xx_, n * sizeof *xx_);
	for (i = 0; i < n; i++)
		ii[i] = i;
	sort(ii, 0, n);
	m = (n + K - 1) / K;
	build_();
}

int k;

void remove_(int i_) {
	int h, i;

	h = hh[i_];
	for (i = 0; i < kk[h]; i++)
		if (iii[h][i] == i_) {
			kk[h]--;
			while (i < kk[h])
				iii[h][i] = iii[h][i + 1], i++;
		}
	build(h);
}

void add(int i_) {
	int h, i;

	for (h = 0; h < m; h++)
		if (kk[h] && xx[iii[h][0]] > xx[i_]) {
			if (h == 0)
				h++;
			break;
		}
	h--;
	kk[h]++;
	for (i = kk[h] - 1; i > 0 && xx[i_] < xx[iii[h][i - 1]]; i--)
		iii[h][i] = iii[h][i - 1];
	iii[h][i] = i_, hh[i_] = h;
	build(h);
}

int solve() {
	int h, x, ans;

	x = -INF, ans = 0;
	for (h = 0; h < m; h++)
		if (kk[h] && xx[iii[h][kk[h] - 1]] - x > d) {
			int lower = -1, upper = kk[h] - 1, i;

			while (upper - lower > 1) {
				i = (lower + upper) / 2;
				if (xx[iii[h][i]] - x <= d)
					lower = i;
				else
					upper = i;
			}
			i = upper;
			ans += cnt[h][i], x = xx_[h][i];
		}
	return ans;
}

int update(int i, int x) {
	if (k == K)
		extract(), build_(), k = 0;
	remove_(i), xx[i] = x, add(i), k++;
	return solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3