Submission #404700

#	Time	Username	Problem	Language	Result	Execution time	Memory
404700		rainboy	Dancing Elephants (IOI11_elephants)	C11	100 / 100	2149 ms	19524 KiB

elephants

/* upsolve using LCT */
#include "elephants.h"

#define N	150000
#define Q	150000

unsigned int X = 12345;

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

int xx[N * 2], 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 zz[1 + N * 2], ll[1 + N * 2], rr[1 + N * 2], ii[1 + N * 2], u_, l_, r_;

int node(int i) {
	static int _ = 1;

	zz[_] = rand_(), ii[_] = i;
	return _++;
}

int first(int u) {
	return ll[u] == 0 ? u : first(ll[u]);
}

int last(int u) {
	return rr[u] == 0 ? u : last(rr[u]);
}

void split(int u, int i) {
	int c;

	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	c = compare(ii[u], i);
	if (c < 0) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else if (c > 0) {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

int tt[1 + N * 2][2], pp[1 + N * 2], sz[1 + N * 2];

int dir(int u) {
	return tt[pp[u]][0] != u;
}

int is_root(int u) {
	return tt[pp[u]][0] != u && tt[pp[u]][1] != u;
}

void pul(int u) {
	int l = tt[u][0], r = tt[u][1];

	sz[u] = sz[l] + sz[r] + (u <= n);
}

void attach(int p, int u, int d) {
	if (p)
		tt[p][d] = u, pul(p);
	if (u)
		pp[u] = p;
}

void rotate(int u) {
	int v = pp[u], w = pp[v], du = dir(u), dv = dir(v);

	if (is_root(v))
		pp[u] = w;
	else
		attach(w, u, dv);
	attach(v, tt[u][du ^ 1], du);
	attach(u, v, du ^ 1);
}

void splay(int u) {
	while (!is_root(u)) {
		int v = pp[u];

		if (!is_root(v))
			rotate(dir(u) == dir(v) ? v : u);
		rotate(u);
	}
}

void expose(int u) {
	int v, w;

	for (w = 0, v = u; v; w = v, v = pp[v])
		splay(v), attach(v, w, 1);
	splay(u);
}

void link(int u, int v) {
	expose(u), expose(v), attach(v, u, 1);
}

void cut(int u) {
	expose(u);
	pp[tt[u][0]] = 0, attach(u, 0, 0);
}

int depth(int u) {
	expose(u);
	return sz[u];
}

void init(int n_, int d_, int *xx_) {
	static int ii[N * 2];
	int i;

	n = n_, d = d_;
	for (i = 0; i < n; i++)
		xx[i] = xx_[i], xx[n + i] = xx[i] + d;
	for (i = 0; i < n * 2; i++)
		ii[i] = i;
	sort(ii, 0, n * 2);
	for (i = 1; i <= n; i++)
		sz[i] = 1;
	for (i = 0; i < n * 2; i++) {
		if (i + 1 < n * 2)
			link(1 + ii[i], 1 + (ii[i] < n ? ii[i] + n : ii[i + 1]));
		u_ = merge(u_, node(ii[i]));
	}
}

int update(int i, int x) {
	int u, v, p;

	split(u_, n + i), v = u_, p = l_ ? ii[last(l_)] : -1;
	if (p >= n) {
		cut(1 + p);
		if (r_)
			link(1 + p, 1 + ii[first(r_)]);
	}
	cut(1 + n + i);
	u_ = merge(l_, r_);
	split(u_, i), u = u_, p = l_ ? ii[last(l_)] : -1;
	if (p >= n) {
		cut(1 + p);
		if (r_)
			link(1 + p, 1 + ii[first(r_)]);
	}
	u_ = merge(l_, r_);
	xx[i] = x, xx[n + i] = xx[i] + d;
	split(u_, n + i), p = l_ ? ii[last(l_)] : -1;
	if (p >= n)
		cut(1 + p), link(1 + p, 1 + n + i);
	if (r_)
		link(1 + n + i, 1 + ii[first(r_)]);
	u_ = merge(merge(l_, v), r_);
	split(u_, i), p = l_ ? ii[last(l_)] : -1;
	if (p >= n)
		cut(1 + p), link(1 + p, 1 + i);
	u_ = merge(merge(l_, u), r_);
	return depth(1 + ii[first(u_)]);
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3