Submission #403162

#	Time	Username	Problem	Language	Result	Execution time	Memory
403162		rainboy	Dancing Elephants (IOI11_elephants)	C11	97 / 100	9028 ms	16232 KiB

elephants

#include "elephants.h"
#include <string.h>

#define N	150000
#define LN	17	/* LN = floor(log2(N)) */
#define K	512
#define INF	0x3f3f3f3f

unsigned int X = 12345;

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

int xx[N * 2], ii[N], n, d;

int compare(int i, int j) { return xx[i] != xx[j] ? xx[i] - xx[j] : i - j; }

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) {
			int c = compare(ii[j], i_);

			if (c == 0)
				j++;
			else if (c < 0) {
				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 pp[LN + 1][N + 1], ii_[K * 2], k;

void build() {
	static int ii1[N];
	int n_, n1, k_, g, i, j, l;

	n_ = 0;
	for (i = 0; i < n; i++)
		if (xx[n + ii[i]] == -1)
			ii[n_++] = ii[i];
	k_ = 0;
	for (g = 0; g < k; g++)
		if (ii_[g] >= n)
			xx[ii_[g] - n] = xx[ii_[g]], xx[ii_[g]] = -1, ii_[k_++] = ii_[g] - n;
	i = 0, j = 0, n1 = 0;
	while (i < n_ || j < k_)
		ii1[n1++] = i < n_ && (j == k_ || compare(ii[i], ii_[j]) < 0) ? ii[i++] : ii_[j++];
	memcpy(ii, ii1, n * sizeof *ii1);
	for (i = 0, j = 0; i < n; i++) {
		while (j < n && xx[ii[j]] - xx[ii[i]] <= d)
			j++;
		pp[0][i] = j;
	}
	pp[0][n] = n;
	for (l = 1; l <= LN; l++)
		for (i = 0; i <= n; i++)
			pp[l][i] = pp[l - 1][pp[l - 1][i]];
	k = 0;
}

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

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

void bubble(int i) {
	int g, tmp;

	for (g = 0; g < k; g++)
		if (ii_[g] == i)
			break;
	while (g > 0 && compare(ii_[g], ii_[g - 1]) < 0)
		tmp = ii_[g], ii_[g] = ii_[g - 1], ii_[g - 1] = tmp, g--;
	while (g + 1 < k && compare(ii_[g], ii_[g + 1]) > 0)
		tmp = ii_[g], ii_[g] = ii_[g + 1], ii_[g + 1] = tmp, g++;
}

int solve() {
	int g, x, h, h_, l, ans;

	ans = 0;
	for (g = 0, x = -INF, h = 0; g < k; g++) {
		int i_ = ii_[g];

		if (h < n && compare(ii[h], i_) < 0) {
			for (l = LN; l >= 0; l--) {
				h_ = pp[l][h];
				if (h_ < n && compare(ii[h_], i_) < 0)
					ans += 1 << l, h = h_;
			}
			ans++, x = xx[ii[h]], h = pp[0][h];
		}
		if (xx[i_] - x <= d)
			continue;
		if (i_ < n)
			h++;
		else {
			ans++, x = xx[i_];
			if (h < n && xx[ii[h]] - x <= d) {
				for (l = LN; l >= 0; l--) {
					h_ = h + (1 << l);
					if (h_ < n && xx[ii[h_]] - x <= d)
						h = h_;
				}
				h++;
			}
		}
	}
	if (h < n) {
		for (l = LN; l >= 0; l--)
			if (pp[l][h] < n)
				ans += 1 << l, h = pp[l][h];
		ans++;
	}
	return ans;
}

int update(int i, int y) {
	if (xx[n + i] == -1) {
		if (k == K * 2)
			build();
		ii_[k++] = i, bubble(i);
		ii_[k++] = n + i, xx[n + i] = y, bubble(n + i);
	} else
		xx[n + i] = y, bubble(n + i);
	return solve();
}

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