oj.uz

Submission #403976

# Submission time Handle Problem Language Result Execution time Memory
403976 2021-05-13T16:08:53 Z rainboy Dancing Elephants (IOI11_elephants) C
100 / 100
 7810 ms 12684 KB 
/* 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

# 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 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

# 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 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

# 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 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