Submission #711968

#	Time	Username	Problem	Language	Result	Execution time	Memory
711968		rainboy	Collapse (JOI18_collapse)	C++17	0 / 100	413 ms	11400 KiB

collapse

#include "collapse.h"

using namespace std;

typedef vector<int> vi;

const int N = 100000, M = 100000, Q = 100000, K = M + Q, N_ = N + M + 1;

unsigned int X = 12345;

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

int n;
int ii[M], jj[M], hh[M], m;
int aa[Q], bb[Q], ans[Q], q;
int ll[K], rr[K], hh_[K], gg[K];

int compare(int h1, int h2) {
	return ii[h1] != ii[h2] ? ii[h1] - ii[h2] : (jj[h1] != jj[h2] ? jj[h1] - jj[h2] : h1 - h2);
}

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
		while (j < k) {
			int c = compare(hh[j], h);
			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		}
		sort(hh, l, i);
		l = k;
	}
}

int tt[N_][2], pp[N_], ww[N_], mx[N_]; char lz[N_];

int dir(int u) {
	return u == tt[pp[u]][0] ? 0 : 1;
}

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

void put(int u) {
	if (u) {
		int tmp;
		tmp = tt[u][0], tt[u][0] = tt[u][1], tt[u][1] = tmp;
		lz[u] ^= 1;
	}
}

void pus(int u) {
	if (lz[u])
		put(tt[u][0]), put(tt[u][1]), lz[u] = 0;
}

void pul(int u) {
	if (!lz[u])
		mx[u] = max(max(mx[tt[u][0]], ww[u]), mx[tt[u][1]]);
}

int argmax(int u) {
	while (1) {
		pus(u);
		if (mx[u] == ww[u])
			return u;
		else
			u = mx[u] == mx[tt[u][0]] ? tt[u][0] : tt[u][1];
	}
}

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

void rotate(int u) {
	int v = pp[u], w = pp[v], du = dir(u), dv = dir(v), special = is_root(v);
	attach(v, tt[u][du ^ 1], du);
	attach(u, v, du ^ 1);
	if (special)
		pp[u] = w;
	else
		attach(w, u, dv);
}

void splay(int u) {
	while (!is_root(u)) {
		int v = pp[u], w = pp[v];
		pus(w), pus(v), pus(u);
		if (is_root(v))
			rotate(u);
		else
			rotate(dir(u) == dir(v) ? v : u), rotate(u);
	}
}

void expose(int u) {
	for (int u_ = u, v = 0; u_; v = u_, u_ = pp[u_])
		splay(u_), pus(u_), attach(u_, v, 1);
	splay(u), put(u);
}

void link(int u, int v) {
	expose(v), expose(u);
	pp[v] = u;
}

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

int argmax_(int u, int v) {
	expose(v), expose(u);
	return pp[v] == 0 ? -1 : argmax(u) - n - 1;
}

int ft[N];

void update(int i, int x) {
	while (i < n) {
		ft[i] += x;
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;
	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

void link_(int h) {
	link(ii[h] + 1, n + 1 + h), link(jj[h] + 1, n + 1 + h);
	update(jj[h], 1);
}

void cut_(int h) {
	cut(ii[h] + 1, n + 1 + h), cut(jj[h] + 1, n + 1 + h);
	update(jj[h], -1);
}

int hh1[M], hh2[M], cnt;

void add(int h) {
	int h_ = argmax_(ii[h] + 1, jj[h] + 1);
	if (h_ == -1 || ww[h_] < ww[h]) {
		hh1[cnt] = h_, hh2[cnt] = h, cnt++;
		if (h_ != -1)
			cut_(h_);
		link_(h);
	} else
		hh1[cnt] = -1, hh2[cnt] = -1, cnt++;
}

void undo() {
	int h1 = hh1[cnt - 1], h2 = hh2[cnt - 1];
	cnt--;
	if (h2 != -1) {
		cut_(h2);
		if (h1 != -1)
			link_(h1);
	}
}

void solve(int *gg, int k, int l, int r) {
	int g1 = 0, g2 = 0, g3 = k, tmp;
	while (g2 < g3)
		if (ll[gg[g2]] <= l && r <= rr[gg[g2]])
			g2++;
		else if (ll[gg[g2]] < r && l < rr[gg[g2]]) {
			tmp = gg[g1], gg[g1] = gg[g2], gg[g2] = tmp;
			g1++, g2++;
		} else {
			g3--;
			tmp = gg[g2], gg[g2] = gg[g3], gg[g3] = tmp;
		}
	for (int g = g1; g < g2; g++) {
		int g_ = gg[g];
		if (hh_[g_] == -1)
			add(ll[g_]);
	}
	if (r - l > 1) {
		int m = (l + r) / 2;
		solve(gg, g1, l, m), solve(gg, g1, m, r);
	} else
		for (int g = g1; g < g2; g++) {
			int g_ = gg[g], h_ = hh_[g_];
			if (h_ != -1)
				ans[h_] -= query(bb[h_]);
		}
	for (int g = g2 - 1; g >= g1; g--) {
		int g_ = gg[g];
		if (hh_[g_] == -1)
			undo();
	}
}

vi simulateCollapse(int n_, vi xx, vi ii_, vi jj_, vi aa_, vi bb_) {
	n = n_, m = ii_.size(), q = aa_.size();
	for (int h = 0; h < m; h++) {
		ii[h] = ii_[h], jj[h] = jj_[h];
		if (ii[h] > jj[h]) {
			int tmp;
			tmp = ii[h], ii[h] = jj[h], jj[h] = tmp;
		}
	}
	for (int h = 0; h < m; h++)
		hh[h] = h;
	sort(hh, 0, m);
	int k = 0;
	for (int h = 0; h < m; h++)
		if (h + 1 < m && ii[hh[h + 1]] == ii[hh[h]] && jj[hh[h + 1]] == jj[hh[h]])
			ll[k] = hh[h], rr[k] = hh[h + 1], hh_[k] = -1, k++, h++;
		else
			ll[k] = hh[h], rr[k] = m, hh_[k] = -1, k++;
	for (int h = 0; h < q; h++) {
		aa[h] = aa_[h], bb[h] = bb_[h];
		ans[h] = n;
		ll[k] = aa[h], rr[k] = aa[h] + 1, hh_[k] = h, k++;
	}
	for (int r = 0; r < 2; r++) {
		for (int h = 0; h < m; h++)
			ww[n + 1 + h] = jj[h] + 1;
		for (int g = 0; g < k; g++)
			gg[g] = g;
		solve(gg, k, 0, m);
		for (int h = 0; h < m; h++) {
			int tmp;
			tmp = n - 1 - ii[h], ii[h] = n - 1 - jj[h], jj[h] = tmp;
		}
		for (int h = 0; h < q; h++)
			bb[h] = n - 2 - bb[h];
	}
	return vi(ans, ans + q);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35