Submission #403123

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

elephants

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

#define N	150000
#define LN	17	/* LN = floor(log2(N)) */
#define K	300
#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() {
	int i, j, l;

	for (i = 0; i < n; i++)
		if (xx[n + i] != -1)
			xx[i] = xx[n + i], xx[n + i] = -1;
	for (i = 0; i < n; i++)
		ii[i] = i;
	sort(ii, 0, n);
	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_) {
	n = n_, d = d_;
	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	746 ms	2032 KB	Output is correct
8	Correct	899 ms	2476 KB	Output is correct
9	Correct	2807 ms	5256 KB	Output is correct
10	Correct	971 ms	5260 KB	Output is correct
11	Correct	964 ms	5260 KB	Output is correct
12	Correct	4136 ms	5256 KB	Output is correct
13	Correct	969 ms	5176 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	746 ms	2032 KB	Output is correct
8	Correct	899 ms	2476 KB	Output is correct
9	Correct	2807 ms	5256 KB	Output is correct
10	Correct	971 ms	5260 KB	Output is correct
11	Correct	964 ms	5260 KB	Output is correct
12	Correct	4136 ms	5256 KB	Output is correct
13	Correct	969 ms	5176 KB	Output is correct
14	Correct	1388 ms	2708 KB	Output is correct
15	Correct	1451 ms	3140 KB	Output is correct
16	Correct	6471 ms	5496 KB	Output is correct
17	Correct	7547 ms	7220 KB	Output is correct
18	Correct	7088 ms	7212 KB	Output is correct
19	Correct	1910 ms	7212 KB	Output is correct
20	Correct	7565 ms	7212 KB	Output is correct
21	Correct	6982 ms	7236 KB	Output is correct
22	Correct	1917 ms	7332 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	746 ms	2032 KB	Output is correct
8	Correct	899 ms	2476 KB	Output is correct
9	Correct	2807 ms	5256 KB	Output is correct
10	Correct	971 ms	5260 KB	Output is correct
11	Correct	964 ms	5260 KB	Output is correct
12	Correct	4136 ms	5256 KB	Output is correct
13	Correct	969 ms	5176 KB	Output is correct
14	Correct	1388 ms	2708 KB	Output is correct
15	Correct	1451 ms	3140 KB	Output is correct
16	Correct	6471 ms	5496 KB	Output is correct
17	Correct	7547 ms	7220 KB	Output is correct
18	Correct	7088 ms	7212 KB	Output is correct
19	Correct	1910 ms	7212 KB	Output is correct
20	Correct	7565 ms	7212 KB	Output is correct
21	Correct	6982 ms	7236 KB	Output is correct
22	Correct	1917 ms	7332 KB	Output is correct
23	Execution timed out	9089 ms	14864 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-