Submission #545937

#	Time	Username	Problem	Language	Result	Execution time	Memory
545937		rainboy	The Potion of Great Power (CEOI20_potion)	C++11	100 / 100	897 ms	43872 KiB

potion

/* 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
• Subtask 2: 17 / 17
• Subtask 3: 14 / 14
• Subtask 4: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 30 / 30