Submission #403908

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
403908	2021-05-13T14:56:49 Z	rainboy	Dancing Elephants (IOI11_elephants)	C	97 / 100	9000 ms	16924 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, k1;

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 && (xx[ii[h]] < xx[i_] || xx[ii[h]] == xx[i_] && ii[h] < i_)) {
			for (l = LN; l >= 0; l--) {
				h_ = pp[h][l];
				if (h_ < n && (xx[ii[h_]] < xx[i_] || xx[ii[h_]] == xx[i_] && ii[h_] < i_))
					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 (k1 == K)
		build(), k1 = 0;
	k1++;
	if (xx[n + i] == -1) {
		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();
}

Compilation message

elephants.c: In function 'solve':
elephants.c:101:59: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  101 |   if (h < n && (xx[ii[h]] < xx[i_] || xx[ii[h]] == xx[i_] && ii[h] < i_)) {
      |                                       ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
elephants.c:104:64: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  104 |     if (h_ < n && (xx[ii[h_]] < xx[i_] || xx[ii[h_]] == xx[i_] && ii[h_] < i_))
      |                                           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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	287 ms	2988 KB	Output is correct
8	Correct	300 ms	3556 KB	Output is correct
9	Correct	1042 ms	6624 KB	Output is correct
10	Correct	452 ms	6564 KB	Output is correct
11	Correct	451 ms	6716 KB	Output is correct
12	Correct	3240 ms	6628 KB	Output is correct
13	Correct	410 ms	6604 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	287 ms	2988 KB	Output is correct
8	Correct	300 ms	3556 KB	Output is correct
9	Correct	1042 ms	6624 KB	Output is correct
10	Correct	452 ms	6564 KB	Output is correct
11	Correct	451 ms	6716 KB	Output is correct
12	Correct	3240 ms	6628 KB	Output is correct
13	Correct	410 ms	6604 KB	Output is correct
14	Correct	1156 ms	3808 KB	Output is correct
15	Correct	463 ms	4292 KB	Output is correct
16	Correct	4595 ms	6864 KB	Output is correct
17	Correct	5261 ms	8740 KB	Output is correct
18	Correct	5143 ms	8740 KB	Output is correct
19	Correct	960 ms	8772 KB	Output is correct
20	Correct	5338 ms	8612 KB	Output is correct
21	Correct	5324 ms	8652 KB	Output is correct
22	Correct	744 ms	8556 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	287 ms	2988 KB	Output is correct
8	Correct	300 ms	3556 KB	Output is correct
9	Correct	1042 ms	6624 KB	Output is correct
10	Correct	452 ms	6564 KB	Output is correct
11	Correct	451 ms	6716 KB	Output is correct
12	Correct	3240 ms	6628 KB	Output is correct
13	Correct	410 ms	6604 KB	Output is correct
14	Correct	1156 ms	3808 KB	Output is correct
15	Correct	463 ms	4292 KB	Output is correct
16	Correct	4595 ms	6864 KB	Output is correct
17	Correct	5261 ms	8740 KB	Output is correct
18	Correct	5143 ms	8740 KB	Output is correct
19	Correct	960 ms	8772 KB	Output is correct
20	Correct	5338 ms	8612 KB	Output is correct
21	Correct	5324 ms	8652 KB	Output is correct
22	Correct	744 ms	8556 KB	Output is correct
23	Execution timed out	9045 ms	16924 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-