Submission #403169

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
403169	2021-05-12T21:35:07 Z	rainboy	Dancing Elephants (IOI11_elephants)	C	97 / 100	9000 ms	15456 KB

elephants

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

#define N	150000
#define LN	17	/* LN = floor(log2(N)) */
#define K	256
#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.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	412 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	412 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	412 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	508 ms	2104 KB	Output is correct
8	Correct	589 ms	2560 KB	Output is correct
9	Correct	2161 ms	5460 KB	Output is correct
10	Correct	295 ms	5460 KB	Output is correct
11	Correct	287 ms	5396 KB	Output is correct
12	Correct	2953 ms	5460 KB	Output is correct
13	Correct	284 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	412 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	508 ms	2104 KB	Output is correct
8	Correct	589 ms	2560 KB	Output is correct
9	Correct	2161 ms	5460 KB	Output is correct
10	Correct	295 ms	5460 KB	Output is correct
11	Correct	287 ms	5396 KB	Output is correct
12	Correct	2953 ms	5460 KB	Output is correct
13	Correct	284 ms	5464 KB	Output is correct
14	Correct	896 ms	2792 KB	Output is correct
15	Correct	947 ms	3300 KB	Output is correct
16	Correct	4665 ms	5688 KB	Output is correct
17	Correct	5189 ms	7492 KB	Output is correct
18	Correct	4868 ms	7496 KB	Output is correct
19	Correct	564 ms	7492 KB	Output is correct
20	Correct	5218 ms	7496 KB	Output is correct
21	Correct	4807 ms	7500 KB	Output is correct
22	Correct	514 ms	7440 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	412 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	508 ms	2104 KB	Output is correct
8	Correct	589 ms	2560 KB	Output is correct
9	Correct	2161 ms	5460 KB	Output is correct
10	Correct	295 ms	5460 KB	Output is correct
11	Correct	287 ms	5396 KB	Output is correct
12	Correct	2953 ms	5460 KB	Output is correct
13	Correct	284 ms	5464 KB	Output is correct
14	Correct	896 ms	2792 KB	Output is correct
15	Correct	947 ms	3300 KB	Output is correct
16	Correct	4665 ms	5688 KB	Output is correct
17	Correct	5189 ms	7492 KB	Output is correct
18	Correct	4868 ms	7496 KB	Output is correct
19	Correct	564 ms	7492 KB	Output is correct
20	Correct	5218 ms	7496 KB	Output is correct
21	Correct	4807 ms	7500 KB	Output is correct
22	Correct	514 ms	7440 KB	Output is correct
23	Execution timed out	9018 ms	15456 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-