Submission #403142

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
403142	2021-05-12T20:07:42 Z	rainboy	Dancing Elephants (IOI11_elephants)	C	97 / 100	9000 ms	15432 KB

elephants

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

#define N	150000
#define LN	17	/* LN = floor(log2(N)) */
#define K	64
#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, 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--)
				if (pp[l][h] < n && compare(ii[pp[l][h]], i_) < 0)
					ans += 1 << l, h = pp[l][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--)
					if (h + (1 << l) < n && xx[ii[h + (1 << l)]] - x <= d)
						h += 1 << l;
				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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct

Subtask #3

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	360 ms	2084 KB	Output is correct
8	Correct	468 ms	2540 KB	Output is correct
9	Correct	870 ms	5464 KB	Output is correct
10	Correct	889 ms	5464 KB	Output is correct
11	Correct	892 ms	5464 KB	Output is correct
12	Correct	1761 ms	5464 KB	Output is correct
13	Correct	847 ms	5464 KB	Output is correct

Subtask #4

47.0 / 47.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	360 ms	2084 KB	Output is correct
8	Correct	468 ms	2540 KB	Output is correct
9	Correct	870 ms	5464 KB	Output is correct
10	Correct	889 ms	5464 KB	Output is correct
11	Correct	892 ms	5464 KB	Output is correct
12	Correct	1761 ms	5464 KB	Output is correct
13	Correct	847 ms	5464 KB	Output is correct
14	Correct	659 ms	2788 KB	Output is correct
15	Correct	921 ms	3296 KB	Output is correct
16	Correct	2656 ms	5700 KB	Output is correct
17	Correct	3511 ms	7492 KB	Output is correct
18	Correct	3534 ms	7496 KB	Output is correct
19	Correct	1665 ms	7544 KB	Output is correct
20	Correct	3420 ms	7492 KB	Output is correct
21	Correct	3389 ms	7488 KB	Output is correct
22	Correct	1677 ms	7496 KB	Output is correct

Subtask #5

0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	360 ms	2084 KB	Output is correct
8	Correct	468 ms	2540 KB	Output is correct
9	Correct	870 ms	5464 KB	Output is correct
10	Correct	889 ms	5464 KB	Output is correct
11	Correct	892 ms	5464 KB	Output is correct
12	Correct	1761 ms	5464 KB	Output is correct
13	Correct	847 ms	5464 KB	Output is correct
14	Correct	659 ms	2788 KB	Output is correct
15	Correct	921 ms	3296 KB	Output is correct
16	Correct	2656 ms	5700 KB	Output is correct
17	Correct	3511 ms	7492 KB	Output is correct
18	Correct	3534 ms	7496 KB	Output is correct
19	Correct	1665 ms	7544 KB	Output is correct
20	Correct	3420 ms	7492 KB	Output is correct
21	Correct	3389 ms	7488 KB	Output is correct
22	Correct	1677 ms	7496 KB	Output is correct
23	Execution timed out	9028 ms	15432 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-