oj.uz

Submission #403218

# Submission time Handle Problem Language Result Execution time Memory
403218 2021-05-12T23:35:50 Z rainboy Dancing Elephants (IOI11_elephants) C
97 / 100
 9000 ms 16176 KB 
#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	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 342 ms 2080 KB Output is correct
8 Correct 364 ms 2504 KB Output is correct
9 Correct 1474 ms 5600 KB Output is correct
10 Correct 468 ms 5580 KB Output is correct
11 Correct 467 ms 5608 KB Output is correct
12 Correct 2820 ms 5600 KB Output is correct
13 Correct 424 ms 5588 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 342 ms 2080 KB Output is correct
8 Correct 364 ms 2504 KB Output is correct
9 Correct 1474 ms 5600 KB Output is correct
10 Correct 468 ms 5580 KB Output is correct
11 Correct 467 ms 5608 KB Output is correct
12 Correct 2820 ms 5600 KB Output is correct
13 Correct 424 ms 5588 KB Output is correct
14 Correct 1010 ms 2788 KB Output is correct
15 Correct 447 ms 3328 KB Output is correct
16 Correct 4128 ms 5840 KB Output is correct
17 Correct 4978 ms 7716 KB Output is correct
18 Correct 5015 ms 7712 KB Output is correct
19 Correct 990 ms 7712 KB Output is correct
20 Correct 4960 ms 7716 KB Output is correct
21 Correct 4910 ms 7748 KB Output is correct
22 Correct 765 ms 7708 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 342 ms 2080 KB Output is correct
8 Correct 364 ms 2504 KB Output is correct
9 Correct 1474 ms 5600 KB Output is correct
10 Correct 468 ms 5580 KB Output is correct
11 Correct 467 ms 5608 KB Output is correct
12 Correct 2820 ms 5600 KB Output is correct
13 Correct 424 ms 5588 KB Output is correct
14 Correct 1010 ms 2788 KB Output is correct
15 Correct 447 ms 3328 KB Output is correct
16 Correct 4128 ms 5840 KB Output is correct
17 Correct 4978 ms 7716 KB Output is correct
18 Correct 5015 ms 7712 KB Output is correct
19 Correct 990 ms 7712 KB Output is correct
20 Correct 4960 ms 7716 KB Output is correct
21 Correct 4910 ms 7748 KB Output is correct
22 Correct 765 ms 7708 KB Output is correct
23 Execution timed out 9096 ms 16176 KB Time limit exceeded
24 Halted 0 ms 0 KB -