Submission #403213

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
403213	2021-05-12T23:28:36 Z	rainboy	Dancing Elephants (IOI11_elephants)	C	97 / 100	9000 ms	15572 KB

elephants

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

#define N	150000
#define LN	17	/* LN = floor(log2(N)) */
#define K	400
#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[N + 1][LN + 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[i][0] = j;
	}
	pp[n][0] = n;
	for (i = n; i >= 0; i--)
		for (l = 1, j = pp[i][0]; l <= LN; l++)
			j = pp[i][l] = pp[j][l - 1];
	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[h][l];
				if (h_ < n && compare(ii[h_], i_) < 0)
					ans += 1 << l, h = h_;
			}
			ans++, x = xx[ii[h]], h = pp[h][0];
		}
		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[h][l] < n)
				ans += 1 << l, h = pp[h][l];
		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	802 ms	2016 KB	Output is correct
8	Correct	872 ms	2476 KB	Output is correct
9	Correct	2808 ms	5460 KB	Output is correct
10	Correct	434 ms	5424 KB	Output is correct
11	Correct	442 ms	5492 KB	Output is correct
12	Correct	3638 ms	5392 KB	Output is correct
13	Correct	438 ms	5448 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	802 ms	2016 KB	Output is correct
8	Correct	872 ms	2476 KB	Output is correct
9	Correct	2808 ms	5460 KB	Output is correct
10	Correct	434 ms	5424 KB	Output is correct
11	Correct	442 ms	5492 KB	Output is correct
12	Correct	3638 ms	5392 KB	Output is correct
13	Correct	438 ms	5448 KB	Output is correct
14	Correct	1287 ms	2708 KB	Output is correct
15	Correct	1354 ms	3228 KB	Output is correct
16	Correct	5826 ms	5632 KB	Output is correct
17	Correct	6518 ms	7424 KB	Output is correct
18	Correct	6007 ms	7428 KB	Output is correct
19	Correct	924 ms	7516 KB	Output is correct
20	Correct	6567 ms	7428 KB	Output is correct
21	Correct	6069 ms	7428 KB	Output is correct
22	Correct	729 ms	7424 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	802 ms	2016 KB	Output is correct
8	Correct	872 ms	2476 KB	Output is correct
9	Correct	2808 ms	5460 KB	Output is correct
10	Correct	434 ms	5424 KB	Output is correct
11	Correct	442 ms	5492 KB	Output is correct
12	Correct	3638 ms	5392 KB	Output is correct
13	Correct	438 ms	5448 KB	Output is correct
14	Correct	1287 ms	2708 KB	Output is correct
15	Correct	1354 ms	3228 KB	Output is correct
16	Correct	5826 ms	5632 KB	Output is correct
17	Correct	6518 ms	7424 KB	Output is correct
18	Correct	6007 ms	7428 KB	Output is correct
19	Correct	924 ms	7516 KB	Output is correct
20	Correct	6567 ms	7428 KB	Output is correct
21	Correct	6069 ms	7428 KB	Output is correct
22	Correct	729 ms	7424 KB	Output is correct
23	Execution timed out	9036 ms	15572 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-