Submission #403155

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
403155	2021-05-12T20:29:14 Z	rainboy	Dancing Elephants (IOI11_elephants)	C	97 / 100	9000 ms	16320 KB

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, 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	2 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	2 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	953 ms	2108 KB	Output is correct
8	Correct	1022 ms	2560 KB	Output is correct
9	Correct	4156 ms	5476 KB	Output is correct
10	Correct	238 ms	5444 KB	Output is correct
11	Correct	226 ms	5468 KB	Output is correct
12	Correct	4851 ms	5468 KB	Output is correct
13	Correct	234 ms	6284 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	2 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	953 ms	2108 KB	Output is correct
8	Correct	1022 ms	2560 KB	Output is correct
9	Correct	4156 ms	5476 KB	Output is correct
10	Correct	238 ms	5444 KB	Output is correct
11	Correct	226 ms	5468 KB	Output is correct
12	Correct	4851 ms	5468 KB	Output is correct
13	Correct	234 ms	6284 KB	Output is correct
14	Correct	1549 ms	3608 KB	Output is correct
15	Correct	1556 ms	4036 KB	Output is correct
16	Correct	7963 ms	6532 KB	Output is correct
17	Correct	8491 ms	8236 KB	Output is correct
18	Correct	7965 ms	8300 KB	Output is correct
19	Correct	465 ms	8308 KB	Output is correct
20	Correct	8601 ms	8308 KB	Output is correct
21	Correct	8052 ms	8308 KB	Output is correct
22	Correct	378 ms	8304 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	2 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	953 ms	2108 KB	Output is correct
8	Correct	1022 ms	2560 KB	Output is correct
9	Correct	4156 ms	5476 KB	Output is correct
10	Correct	238 ms	5444 KB	Output is correct
11	Correct	226 ms	5468 KB	Output is correct
12	Correct	4851 ms	5468 KB	Output is correct
13	Correct	234 ms	6284 KB	Output is correct
14	Correct	1549 ms	3608 KB	Output is correct
15	Correct	1556 ms	4036 KB	Output is correct
16	Correct	7963 ms	6532 KB	Output is correct
17	Correct	8491 ms	8236 KB	Output is correct
18	Correct	7965 ms	8300 KB	Output is correct
19	Correct	465 ms	8308 KB	Output is correct
20	Correct	8601 ms	8308 KB	Output is correct
21	Correct	8052 ms	8308 KB	Output is correct
22	Correct	378 ms	8304 KB	Output is correct
23	Execution timed out	9071 ms	16320 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-