oj.uz

Submission #545937

# Submission time Handle Problem Language Result Execution time Memory
545937 2022-04-05T16:14:50 Z rainboy The Potion of Great Power (CEOI20_potion) C++11
100 / 100
 897 ms 43872 KB 
/* https://codeforces.com/blog/entry/82022 */
#include <stdlib.h>
#include <string.h>

#define N	100000
#define M	200000
#define D	500
#define B	50	/* B = floor(sqrt(M)) */
#define K	(M / B)
#define INF	1000000000

int abs_(int a) { return a > 0 ? a : -a; }
int min(int a, int b) { return a < b ? a : b; }

int aa[N], n, d;

void init(int n_, int d_, int *aa_) {
	memcpy(aa, aa_, (n = n_) * sizeof *aa_), d = d_;
}

int *jj[N], kk[N], *eh[N], *ep[N], *eq[N], **ejj[N], eo[N];

void append(int i, int h, int p, int q) {
	int o = eo[i]++;

	eh[i][o] = h, ep[i][o] = p, eq[i][o] = q;
	if ((o + 1) % B == 0)
		memcpy(ejj[i][o / B], jj[i], kk[i] * sizeof *jj[i]);
}

void update(int i, int j, int h) {
	int g;

	for (g = 0; g < kk[i]; g++)
		if (jj[i][g] == j) {
			int p;

			p = g == 0 ? n : jj[i][g - 1];
			kk[i]--;
			for  ( ; g < kk[i]; g++)
				jj[i][g] = jj[i][g + 1];
			append(i, h, p, j);
			return;
		}
	kk[i]++;
	for (g = kk[i] - 1; g > 0 && aa[jj[i][g - 1]] > aa[j]; g--)
		jj[i][g] = jj[i][g - 1];
	jj[i][g] = j;
	append(i, h, g == 0 ? n : jj[i][g - 1], j);
}

void curseChanges(int m, int *uu, int *vv) {
	int g, h, i, j;

	for (h = 0; h < m; h++) {
		i = uu[h], j = vv[h];
		eo[i]++, eo[j]++;
	}
	for (i = 0; i < n; i++) {
		int k;

		jj[i] = (int *) malloc(eo[i] * sizeof *jj[i]);
		eh[i] = (int *) malloc(eo[i] * sizeof *eh[i]);
		ep[i] = (int *) malloc(eo[i] * sizeof *ep[i]);
		eq[i] = (int *) malloc(eo[i] * sizeof *eq[i]);
		ejj[i] = (int **) malloc((k = eo[i] / B) * sizeof *ejj[i]);
		for (g = 0; g < k; g++) {
			ejj[i][g] = (int *) malloc(d * sizeof *ejj[i][g]);
			memset(ejj[i][g], -1, d * sizeof *ejj[i][g]);
		}
		eo[i] = 0;
	}
	for (h = 0; h < m; h++) {
		i = uu[h], j = vv[h];
		update(i, j, h), update(j, i, h);
	}
}

int next[N + 1];

int query_(int *aa_, int i, int o) {
	int g = (o + 1) / B - 1, h, j, o_, cnt;

	if (g == -1)
		next[n] = -1;
	else {
		for (h = 0; h < d && ejj[i][g][h] != -1; h++)
			next[h == 0 ? n : ejj[i][g][h - 1]] = ejj[i][g][h];
		next[h == 0 ? n : ejj[i][g][h - 1]] = -1;
	}
	for (o_ = (g + 1) * B; o_ <= o; o_++) {
		int p = ep[i][o_], q = eq[i][o_];

		if (next[p] != q)
			next[q] = next[p], next[p] = q;
		else
			next[p] = next[q];
	}
	cnt = 0;
	for (j = next[n]; j != -1; j = next[j])
		aa_[cnt++] = aa[j];
	return cnt;
}

int query(int *aa, int i, int h) {
	int lower = -1, upper = eo[i];

	while (upper - lower > 1) {
		int o = (lower + upper) / 2;

		if (eh[i][o] < h)
			lower = o;
		else
			upper = o;
	}
	return query_(aa, i, lower);
}

int question(int i, int j, int h_) {
	static int aa[D], bb[D];
	int n, m, ans;

	n = query(aa, i, h_), m = query(bb, j, h_);
	i = 0, j = 0, ans = INF;
	while (i < n && j < m) {
		ans = min(ans, abs_(aa[i] - bb[j]));
		if (aa[i] < bb[j])
			i++;
		else
			j++;
	}
	return ans;
}

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 464 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 28 ms 21812 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 24216 KB Output is correct
2 Correct 155 ms 24216 KB Output is correct
3 Correct 159 ms 43872 KB Output is correct
4 Correct 412 ms 23076 KB Output is correct
5 Correct 167 ms 10960 KB Output is correct
6 Correct 829 ms 33812 KB Output is correct
7 Correct 260 ms 32984 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 24124 KB Output is correct
2 Correct 672 ms 33616 KB Output is correct
3 Correct 443 ms 33836 KB Output is correct
4 Correct 732 ms 33804 KB Output is correct
5 Correct 201 ms 25024 KB Output is correct
6 Correct 763 ms 33744 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2496 KB Output is correct
2 Correct 53 ms 3168 KB Output is correct
3 Correct 80 ms 3128 KB Output is correct
4 Correct 202 ms 3012 KB Output is correct
5 Correct 196 ms 2752 KB Output is correct
6 Correct 58 ms 776 KB Output is correct
7 Correct 195 ms 3144 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 2 ms 464 KB Output is correct
5 Correct 28 ms 21812 KB Output is correct
6 Correct 150 ms 24216 KB Output is correct
7 Correct 155 ms 24216 KB Output is correct
8 Correct 159 ms 43872 KB Output is correct
9 Correct 412 ms 23076 KB Output is correct
10 Correct 167 ms 10960 KB Output is correct
11 Correct 829 ms 33812 KB Output is correct
12 Correct 260 ms 32984 KB Output is correct
13 Correct 164 ms 24124 KB Output is correct
14 Correct 672 ms 33616 KB Output is correct
15 Correct 443 ms 33836 KB Output is correct
16 Correct 732 ms 33804 KB Output is correct
17 Correct 201 ms 25024 KB Output is correct
18 Correct 763 ms 33744 KB Output is correct
19 Correct 42 ms 2496 KB Output is correct
20 Correct 53 ms 3168 KB Output is correct
21 Correct 80 ms 3128 KB Output is correct
22 Correct 202 ms 3012 KB Output is correct
23 Correct 196 ms 2752 KB Output is correct
24 Correct 58 ms 776 KB Output is correct
25 Correct 195 ms 3144 KB Output is correct
26 Correct 375 ms 33808 KB Output is correct
27 Correct 496 ms 33824 KB Output is correct
28 Correct 550 ms 29112 KB Output is correct
29 Correct 436 ms 23180 KB Output is correct
30 Correct 897 ms 33700 KB Output is correct
31 Correct 845 ms 33568 KB Output is correct
32 Correct 882 ms 33732 KB Output is correct