Submission #403216

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
403216	2021-05-12T23:33:23 Z	rainboy	Dancing Elephants (IOI11_elephants)	C	97 / 100	9000 ms	16124 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], jump[N], 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_], h = jump[i_ - n];
	}
	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) {
	int lower, upper;

	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);
	lower = -1, upper = n;
	while (upper - lower > 1) {
		int h = (lower + upper) / 2;

		if (xx[ii[h]] - xx[n + i] <= d)
			lower = h;
		else
			upper = h;
	}
	jump[i] = upper;
	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	264 ms	2012 KB	Output is correct
8	Correct	303 ms	2508 KB	Output is correct
9	Correct	1840 ms	5608 KB	Output is correct
10	Correct	446 ms	5604 KB	Output is correct
11	Correct	457 ms	5712 KB	Output is correct
12	Correct	3595 ms	5604 KB	Output is correct
13	Correct	406 ms	5632 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	264 ms	2012 KB	Output is correct
8	Correct	303 ms	2508 KB	Output is correct
9	Correct	1840 ms	5608 KB	Output is correct
10	Correct	446 ms	5604 KB	Output is correct
11	Correct	457 ms	5712 KB	Output is correct
12	Correct	3595 ms	5604 KB	Output is correct
13	Correct	406 ms	5632 KB	Output is correct
14	Correct	1264 ms	2788 KB	Output is correct
15	Correct	423 ms	3396 KB	Output is correct
16	Correct	5100 ms	5892 KB	Output is correct
17	Correct	6021 ms	7712 KB	Output is correct
18	Correct	5926 ms	7716 KB	Output is correct
19	Correct	939 ms	7728 KB	Output is correct
20	Correct	6069 ms	7716 KB	Output is correct
21	Correct	6092 ms	7784 KB	Output is correct
22	Correct	748 ms	7760 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	264 ms	2012 KB	Output is correct
8	Correct	303 ms	2508 KB	Output is correct
9	Correct	1840 ms	5608 KB	Output is correct
10	Correct	446 ms	5604 KB	Output is correct
11	Correct	457 ms	5712 KB	Output is correct
12	Correct	3595 ms	5604 KB	Output is correct
13	Correct	406 ms	5632 KB	Output is correct
14	Correct	1264 ms	2788 KB	Output is correct
15	Correct	423 ms	3396 KB	Output is correct
16	Correct	5100 ms	5892 KB	Output is correct
17	Correct	6021 ms	7712 KB	Output is correct
18	Correct	5926 ms	7716 KB	Output is correct
19	Correct	939 ms	7728 KB	Output is correct
20	Correct	6069 ms	7716 KB	Output is correct
21	Correct	6092 ms	7784 KB	Output is correct
22	Correct	748 ms	7760 KB	Output is correct
23	Execution timed out	9012 ms	16124 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-