oj.uz

Submission #404700

# Submission time Handle Problem Language Result Execution time Memory
404700 2021-05-14T20:53:30 Z rainboy Dancing Elephants (IOI11_elephants) C
100 / 100
 2149 ms 19524 KB 
/* 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.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 448 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 448 KB Output is correct
7 Correct 163 ms 2856 KB Output is correct
8 Correct 167 ms 3380 KB Output is correct
9 Correct 318 ms 6576 KB Output is correct
10 Correct 148 ms 6360 KB Output is correct
11 Correct 150 ms 6356 KB Output is correct
12 Correct 433 ms 6452 KB Output is correct
13 Correct 156 ms 6156 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 448 KB Output is correct
7 Correct 163 ms 2856 KB Output is correct
8 Correct 167 ms 3380 KB Output is correct
9 Correct 318 ms 6576 KB Output is correct
10 Correct 148 ms 6360 KB Output is correct
11 Correct 150 ms 6356 KB Output is correct
12 Correct 433 ms 6452 KB Output is correct
13 Correct 156 ms 6156 KB Output is correct
14 Correct 306 ms 4228 KB Output is correct
15 Correct 269 ms 4608 KB Output is correct
16 Correct 578 ms 7120 KB Output is correct
17 Correct 672 ms 9028 KB Output is correct
18 Correct 624 ms 8848 KB Output is correct
19 Correct 200 ms 8984 KB Output is correct
20 Correct 701 ms 8932 KB Output is correct
21 Correct 666 ms 8900 KB Output is correct
22 Correct 232 ms 8388 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 448 KB Output is correct
7 Correct 163 ms 2856 KB Output is correct
8 Correct 167 ms 3380 KB Output is correct
9 Correct 318 ms 6576 KB Output is correct
10 Correct 148 ms 6360 KB Output is correct
11 Correct 150 ms 6356 KB Output is correct
12 Correct 433 ms 6452 KB Output is correct
13 Correct 156 ms 6156 KB Output is correct
14 Correct 306 ms 4228 KB Output is correct
15 Correct 269 ms 4608 KB Output is correct
16 Correct 578 ms 7120 KB Output is correct
17 Correct 672 ms 9028 KB Output is correct
18 Correct 624 ms 8848 KB Output is correct
19 Correct 200 ms 8984 KB Output is correct
20 Correct 701 ms 8932 KB Output is correct
21 Correct 666 ms 8900 KB Output is correct
22 Correct 232 ms 8388 KB Output is correct
23 Correct 1366 ms 19392 KB Output is correct
24 Correct 1305 ms 19524 KB Output is correct
25 Correct 1184 ms 19524 KB Output is correct
26 Correct 481 ms 19524 KB Output is correct
27 Correct 449 ms 19256 KB Output is correct
28 Correct 743 ms 5392 KB Output is correct
29 Correct 717 ms 5388 KB Output is correct
30 Correct 727 ms 5316 KB Output is correct
31 Correct 744 ms 5444 KB Output is correct
32 Correct 477 ms 18824 KB Output is correct
33 Correct 448 ms 18156 KB Output is correct
34 Correct 428 ms 19140 KB Output is correct
35 Correct 458 ms 19328 KB Output is correct
36 Correct 1157 ms 18808 KB Output is correct
37 Correct 1828 ms 19316 KB Output is correct
38 Correct 523 ms 18044 KB Output is correct
39 Correct 459 ms 18968 KB Output is correct
40 Correct 541 ms 18068 KB Output is correct
41 Correct 2089 ms 18904 KB Output is correct
42 Correct 2149 ms 19056 KB Output is correct