Submission #403127

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

elephants

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include "elephants.h"
#include <string.h>

#define N	150000
#define LN	17	/* LN = floor(log2(N)) */
#define K	200
#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	687 ms	2060 KB	Output is correct
8	Correct	835 ms	2500 KB	Output is correct
9	Correct	1856 ms	5280 KB	Output is correct
10	Correct	1315 ms	5364 KB	Output is correct
11	Correct	1295 ms	5316 KB	Output is correct
12	Correct	3584 ms	5296 KB	Output is correct
13	Correct	1326 ms	5292 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	687 ms	2060 KB	Output is correct
8	Correct	835 ms	2500 KB	Output is correct
9	Correct	1856 ms	5280 KB	Output is correct
10	Correct	1315 ms	5364 KB	Output is correct
11	Correct	1295 ms	5316 KB	Output is correct
12	Correct	3584 ms	5296 KB	Output is correct
13	Correct	1326 ms	5292 KB	Output is correct
14	Correct	1250 ms	2724 KB	Output is correct
15	Correct	1459 ms	3232 KB	Output is correct
16	Correct	5371 ms	5516 KB	Output is correct
17	Correct	6769 ms	7232 KB	Output is correct
18	Correct	6440 ms	7228 KB	Output is correct
19	Correct	2590 ms	7224 KB	Output is correct
20	Correct	6720 ms	7236 KB	Output is correct
21	Correct	6388 ms	7228 KB	Output is correct
22	Correct	2520 ms	7228 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	687 ms	2060 KB	Output is correct
8	Correct	835 ms	2500 KB	Output is correct
9	Correct	1856 ms	5280 KB	Output is correct
10	Correct	1315 ms	5364 KB	Output is correct
11	Correct	1295 ms	5316 KB	Output is correct
12	Correct	3584 ms	5296 KB	Output is correct
13	Correct	1326 ms	5292 KB	Output is correct
14	Correct	1250 ms	2724 KB	Output is correct
15	Correct	1459 ms	3232 KB	Output is correct
16	Correct	5371 ms	5516 KB	Output is correct
17	Correct	6769 ms	7232 KB	Output is correct
18	Correct	6440 ms	7228 KB	Output is correct
19	Correct	2590 ms	7224 KB	Output is correct
20	Correct	6720 ms	7236 KB	Output is correct
21	Correct	6388 ms	7228 KB	Output is correct
22	Correct	2520 ms	7228 KB	Output is correct
23	Execution timed out	9021 ms	14964 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-