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
#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();
}
# 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
# 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
# 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
# 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
# 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 -