oj.uz

Submission #711985

# Submission time Handle Problem Language Result Execution time Memory
711985 2023-03-17T20:05:31 Z rainboy Collapse (JOI18_collapse) C++17
100 / 100
 2426 ms 17536 KB 
#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 || jj[h_] > jj[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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 976 KB Output is correct
2 Correct 3 ms 572 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 17 ms 972 KB Output is correct
6 Correct 41 ms 1020 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 14 ms 1092 KB Output is correct
10 Correct 30 ms 1136 KB Output is correct
11 Correct 63 ms 1164 KB Output is correct
12 Correct 37 ms 1128 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5428 KB Output is correct
2 Correct 35 ms 5420 KB Output is correct
3 Correct 360 ms 12748 KB Output is correct
4 Correct 40 ms 5416 KB Output is correct
5 Correct 821 ms 13040 KB Output is correct
6 Correct 107 ms 6188 KB Output is correct
7 Correct 1494 ms 14132 KB Output is correct
8 Correct 418 ms 13792 KB Output is correct
9 Correct 31 ms 5844 KB Output is correct
10 Correct 38 ms 6476 KB Output is correct
11 Correct 69 ms 8176 KB Output is correct
12 Correct 448 ms 16052 KB Output is correct
13 Correct 1282 ms 16568 KB Output is correct
14 Correct 2393 ms 17464 KB Output is correct
15 Correct 1136 ms 17480 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5448 KB Output is correct
2 Correct 38 ms 5424 KB Output is correct
3 Correct 37 ms 5452 KB Output is correct
4 Correct 46 ms 5452 KB Output is correct
5 Correct 75 ms 5684 KB Output is correct
6 Correct 94 ms 6220 KB Output is correct
7 Correct 1138 ms 12388 KB Output is correct
8 Correct 2417 ms 15368 KB Output is correct
9 Correct 33 ms 5808 KB Output is correct
10 Correct 79 ms 8116 KB Output is correct
11 Correct 1262 ms 17488 KB Output is correct
12 Correct 2348 ms 17464 KB Output is correct
13 Correct 1700 ms 17464 KB Output is correct
14 Correct 2410 ms 17456 KB Output is correct
15 Correct 1427 ms 17484 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 976 KB Output is correct
2 Correct 3 ms 572 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 17 ms 972 KB Output is correct
6 Correct 41 ms 1020 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 14 ms 1092 KB Output is correct
10 Correct 30 ms 1136 KB Output is correct
11 Correct 63 ms 1164 KB Output is correct
12 Correct 37 ms 1128 KB Output is correct
13 Correct 26 ms 5428 KB Output is correct
14 Correct 35 ms 5420 KB Output is correct
15 Correct 360 ms 12748 KB Output is correct
16 Correct 40 ms 5416 KB Output is correct
17 Correct 821 ms 13040 KB Output is correct
18 Correct 107 ms 6188 KB Output is correct
19 Correct 1494 ms 14132 KB Output is correct
20 Correct 418 ms 13792 KB Output is correct
21 Correct 31 ms 5844 KB Output is correct
22 Correct 38 ms 6476 KB Output is correct
23 Correct 69 ms 8176 KB Output is correct
24 Correct 448 ms 16052 KB Output is correct
25 Correct 1282 ms 16568 KB Output is correct
26 Correct 2393 ms 17464 KB Output is correct
27 Correct 1136 ms 17480 KB Output is correct
28 Correct 26 ms 5448 KB Output is correct
29 Correct 38 ms 5424 KB Output is correct
30 Correct 37 ms 5452 KB Output is correct
31 Correct 46 ms 5452 KB Output is correct
32 Correct 75 ms 5684 KB Output is correct
33 Correct 94 ms 6220 KB Output is correct
34 Correct 1138 ms 12388 KB Output is correct
35 Correct 2417 ms 15368 KB Output is correct
36 Correct 33 ms 5808 KB Output is correct
37 Correct 79 ms 8116 KB Output is correct
38 Correct 1262 ms 17488 KB Output is correct
39 Correct 2348 ms 17464 KB Output is correct
40 Correct 1700 ms 17464 KB Output is correct
41 Correct 2410 ms 17456 KB Output is correct
42 Correct 1427 ms 17484 KB Output is correct
43 Correct 375 ms 13340 KB Output is correct
44 Correct 1662 ms 14068 KB Output is correct
45 Correct 396 ms 13792 KB Output is correct
46 Correct 2426 ms 15460 KB Output is correct
47 Correct 37 ms 5808 KB Output is correct
48 Correct 65 ms 6360 KB Output is correct
49 Correct 65 ms 8148 KB Output is correct
50 Correct 170 ms 9288 KB Output is correct
51 Correct 489 ms 15932 KB Output is correct
52 Correct 739 ms 16236 KB Output is correct
53 Correct 769 ms 16348 KB Output is correct
54 Correct 825 ms 16692 KB Output is correct
55 Correct 960 ms 16556 KB Output is correct
56 Correct 1146 ms 17048 KB Output is correct
57 Correct 1525 ms 17180 KB Output is correct
58 Correct 1605 ms 17204 KB Output is correct
59 Correct 1329 ms 17536 KB Output is correct
60 Correct 2375 ms 17512 KB Output is correct