답안 #403976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
403976	2021-05-13T16:08:53 Z	rainboy	코끼리 (Dancing Elephants) (IOI11_elephants)	C	100 / 100	7810 ms	12684 KB

elephants

/* upsolve after reading solution */
#include "elephants.h"
#include <string.h>

#define N	150000
#define K	1000
#define	M	150
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int xx[N], ii[N], hh[N], n, d;

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)
			if (xx[ii[j]] == xx[i_])
				j++;
			else if (xx[ii[j]] < xx[i_]) {
				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 iii[M][K * 2], cnt[M][K * 2], xx_[M][K * 2], kk[M], m;

void build(int h) {
	int i, j;

	for (i = kk[h] - 1, j = kk[h]; i >= 0; i--) {
		int x = xx[iii[h][i]];

		while (xx[iii[h][j - 1]] - x > d)
			j--;
		if (j == kk[h])
			cnt[h][i] = 1, xx_[h][i] = x;
		else
			cnt[h][i] = cnt[h][j] + 1, xx_[h][i] = xx_[h][j];
	}
}

void build_() {
	int h, i;

	for (h = 0; h < m; h++) {
		int l = h * K, r = min((h + 1) * K, n);

		kk[h] = r - l;
		for (i = l; i < r; i++)
			iii[h][i - l] = ii[i], hh[ii[i]] = h;
		build(h);
	}
}

void extract() {
	int h, h_, i;

	for (h = 0, h_ = 0; h < m; h++)
		for (i = 0; i < kk[h]; i++)
			ii[h_++] = iii[h][i];
}

void init(int n_, int d_, int *xx_) {
	int i;

	n = n_, d = d_, memcpy(xx, xx_, n * sizeof *xx_);
	for (i = 0; i < n; i++)
		ii[i] = i;
	sort(ii, 0, n);
	m = (n + K - 1) / K;
	build_();
}

int k;

void remove_(int i_) {
	int h, i;

	h = hh[i_];
	for (i = 0; i < kk[h]; i++)
		if (iii[h][i] == i_) {
			kk[h]--;
			while (i < kk[h])
				iii[h][i] = iii[h][i + 1], i++;
		}
	build(h);
}

void add(int i_) {
	int h, i;

	for (h = 0; h < m; h++)
		if (kk[h] && xx[iii[h][0]] > xx[i_]) {
			if (h == 0)
				h++;
			break;
		}
	h--;
	kk[h]++;
	for (i = kk[h] - 1; i > 0 && xx[i_] < xx[iii[h][i - 1]]; i--)
		iii[h][i] = iii[h][i - 1];
	iii[h][i] = i_, hh[i_] = h;
	build(h);
}

int solve() {
	int h, x, ans;

	x = -INF, ans = 0;
	for (h = 0; h < m; h++)
		if (kk[h] && xx[iii[h][kk[h] - 1]] - x > d) {
			int lower = -1, upper = kk[h] - 1, i;

			while (upper - lower > 1) {
				i = (lower + upper) / 2;
				if (xx[iii[h][i]] - x <= d)
					lower = i;
				else
					upper = i;
			}
			i = upper;
			ans += cnt[h][i], x = xx_[h][i];
		}
	return ans;
}

int update(int i, int x) {
	if (k == K)
		extract(), build_(), k = 0;
	remove_(i), xx[i] = x, add(i), k++;
	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	765 ms	1396 KB	Output is correct
8	Correct	833 ms	1592 KB	Output is correct
9	Correct	686 ms	2852 KB	Output is correct
10	Correct	645 ms	2776 KB	Output is correct
11	Correct	608 ms	2884 KB	Output is correct
12	Correct	1252 ms	2864 KB	Output is correct
13	Correct	665 ms	2868 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	765 ms	1396 KB	Output is correct
8	Correct	833 ms	1592 KB	Output is correct
9	Correct	686 ms	2852 KB	Output is correct
10	Correct	645 ms	2776 KB	Output is correct
11	Correct	608 ms	2884 KB	Output is correct
12	Correct	1252 ms	2864 KB	Output is correct
13	Correct	665 ms	2868 KB	Output is correct
14	Correct	632 ms	1952 KB	Output is correct
15	Correct	1199 ms	2056 KB	Output is correct
16	Correct	2233 ms	3092 KB	Output is correct
17	Correct	2251 ms	3876 KB	Output is correct
18	Correct	2378 ms	3876 KB	Output is correct
19	Correct	1211 ms	3872 KB	Output is correct
20	Correct	2200 ms	3904 KB	Output is correct
21	Correct	2077 ms	3884 KB	Output is correct
22	Correct	1081 ms	3880 KB	Output is correct

Subtask #5
3.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	765 ms	1396 KB	Output is correct
8	Correct	833 ms	1592 KB	Output is correct
9	Correct	686 ms	2852 KB	Output is correct
10	Correct	645 ms	2776 KB	Output is correct
11	Correct	608 ms	2884 KB	Output is correct
12	Correct	1252 ms	2864 KB	Output is correct
13	Correct	665 ms	2868 KB	Output is correct
14	Correct	632 ms	1952 KB	Output is correct
15	Correct	1199 ms	2056 KB	Output is correct
16	Correct	2233 ms	3092 KB	Output is correct
17	Correct	2251 ms	3876 KB	Output is correct
18	Correct	2378 ms	3876 KB	Output is correct
19	Correct	1211 ms	3872 KB	Output is correct
20	Correct	2200 ms	3904 KB	Output is correct
21	Correct	2077 ms	3884 KB	Output is correct
22	Correct	1081 ms	3880 KB	Output is correct
23	Correct	5157 ms	7924 KB	Output is correct
24	Correct	5631 ms	8052 KB	Output is correct
25	Correct	4220 ms	8056 KB	Output is correct
26	Correct	5006 ms	8056 KB	Output is correct
27	Correct	5018 ms	8056 KB	Output is correct
28	Correct	2705 ms	2380 KB	Output is correct
29	Correct	2686 ms	2372 KB	Output is correct
30	Correct	2737 ms	2380 KB	Output is correct
31	Correct	2712 ms	2376 KB	Output is correct
32	Correct	3811 ms	8312 KB	Output is correct
33	Correct	2605 ms	8308 KB	Output is correct
34	Correct	3913 ms	8312 KB	Output is correct
35	Correct	2407 ms	8308 KB	Output is correct
36	Correct	1696 ms	8312 KB	Output is correct
37	Correct	5785 ms	8312 KB	Output is correct
38	Correct	4191 ms	8312 KB	Output is correct
39	Correct	4257 ms	8388 KB	Output is correct
40	Correct	4054 ms	8312 KB	Output is correct
41	Correct	7443 ms	8312 KB	Output is correct
42	Correct	7810 ms	12684 KB	Output is correct

답안 #403976

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 16.0 / 16.0

Subtask #3 24.0 / 24.0

Subtask #4 47.0 / 47.0

Subtask #5 3.0 / 3.0

Subtask #1
10.0 / 10.0

Subtask #2
16.0 / 16.0

Subtask #3
24.0 / 24.0

Subtask #4
47.0 / 47.0

Subtask #5
3.0 / 3.0