oj.uz

답안 #403170

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403170 2021-05-12T21:36:12 Z rainboy 코끼리 (Dancing Elephants) (IOI11_elephants) C
97 / 100
 9000 ms 15480 KB 
#include "elephants.h"
#include <string.h>

#define N	150000
#define LN	17	/* LN = floor(log2(N)) */
#define K	324
#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[LN + 1][N + 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[0][i] = j;
	}
	pp[0][n] = n;
	for (l = 1; l <= LN; l++)
		for (i = 0; i <= n; i++)
			pp[l][i] = pp[l - 1][pp[l - 1][i]];
	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[l][h];
				if (h_ < n && compare(ii[h_], i_) < 0)
					ans += 1 << l, h = h_;
			}
			ans++, x = xx[ii[h]], h = pp[0][h];
		}
		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[l][h] < n)
				ans += 1 << l, h = pp[l][h];
		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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 626 ms 2088 KB Output is correct
8 Correct 719 ms 2544 KB Output is correct
9 Correct 2730 ms 5464 KB Output is correct
10 Correct 262 ms 5368 KB Output is correct
11 Correct 259 ms 5468 KB Output is correct
12 Correct 3611 ms 5460 KB Output is correct
13 Correct 257 ms 5464 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 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 626 ms 2088 KB Output is correct
8 Correct 719 ms 2544 KB Output is correct
9 Correct 2730 ms 5464 KB Output is correct
10 Correct 262 ms 5368 KB Output is correct
11 Correct 259 ms 5468 KB Output is correct
12 Correct 3611 ms 5460 KB Output is correct
13 Correct 257 ms 5464 KB Output is correct
14 Correct 1062 ms 2756 KB Output is correct
15 Correct 1097 ms 3360 KB Output is correct
16 Correct 5464 ms 5688 KB Output is correct
17 Correct 6167 ms 7488 KB Output is correct
18 Correct 5839 ms 7488 KB Output is correct
19 Correct 516 ms 7452 KB Output is correct
20 Correct 6233 ms 7492 KB Output is correct
21 Correct 5831 ms 7492 KB Output is correct
22 Correct 474 ms 7492 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 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 626 ms 2088 KB Output is correct
8 Correct 719 ms 2544 KB Output is correct
9 Correct 2730 ms 5464 KB Output is correct
10 Correct 262 ms 5368 KB Output is correct
11 Correct 259 ms 5468 KB Output is correct
12 Correct 3611 ms 5460 KB Output is correct
13 Correct 257 ms 5464 KB Output is correct
14 Correct 1062 ms 2756 KB Output is correct
15 Correct 1097 ms 3360 KB Output is correct
16 Correct 5464 ms 5688 KB Output is correct
17 Correct 6167 ms 7488 KB Output is correct
18 Correct 5839 ms 7488 KB Output is correct
19 Correct 516 ms 7452 KB Output is correct
20 Correct 6233 ms 7492 KB Output is correct
21 Correct 5831 ms 7492 KB Output is correct
22 Correct 474 ms 7492 KB Output is correct
23 Execution timed out 9034 ms 15480 KB Time limit exceeded
24 Halted 0 ms 0 KB -