oj.uz

Submission #1020541

# Submission time Handle Problem Language Result Execution time Memory
1020541 2024-07-12T06:49:23 Z BuzzyBeez Tree Rotations (POI11_rot) C++17
72 / 100
 148 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 4e5;

int a[N + 8];
vector<int> adj[N + 8];
set<int> _list[N + 8];
long long inv[N + 8];
int sz[N + 8];

int n, tmp, id = 1;
void input() {
	int x; cin >> x;
	if (x) {_list[id].insert(x); ++sz[id]; a[id] = x; return;}
	int t = id;
	adj[t].push_back(id + 1);
	++id; input();
	adj[t].push_back(id + 1);
	++id; input();
}

void DFS_sz(int u, int p) {for (int v : adj[u]) DFS_sz(v, u), sz[u] += sz[v];}

struct Binary_Indexed_Tree {
	vector<int> BIT;
	
	Binary_Indexed_Tree() {BIT.assign(N + 8, 0);}
	
	int pt;
	void update(int u, int v) {
		pt = u;
		while (pt <= N) {
			BIT[pt] += v;
			pt += pt & -pt;
		}
	}
	
	int res;
	int pf(int p) {
		if (p <= 0) return 0;
		res = 0; pt = p;
		while (pt) {
			res += BIT[pt];
			pt -= pt & -pt;
		}
		return res;
	}
	
	int range(int l, int r) {
		if (l > r) return 0;
		return pf(r) - pf(l - 1);
	}
} tree;

int costLR, costRL;
void DFS(int u, int p) {
	if (sz[u] > 1) { 
		int L = adj[u][0], R = adj[u][1];
		if (sz[L] < sz[R]) swap(L, R);
		// cout << u << " -> " << R << endl;
		DFS(R, u);
		inv[u] += inv[R];
		for (int item : _list[R]) tree.update(item, -1);
		// cout << u << " -> " << L << endl;
		DFS(L, u);
		inv[u] += inv[L];
		costLR = costRL = 0;
		for (int item : _list[R]) costLR += tree.range(item + 1, n), costRL += tree.range(1, item - 1);
		inv[u] += min(costLR, costRL);
		for (int item : _list[R]) tree.update(item, +1);
	}
	if (a[u]) tree.update(a[u], +1);
	for (int v : adj[u]) {
		if (_list[u].size() < _list[v].size()) swap(_list[u], _list[v]);
		for (int item : _list[v]) _list[u].insert(item);
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n; input();
	DFS_sz(1, 0); 
	DFS(1, 0); cout << inv[1];
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 30040 KB Output is correct
2 Correct 12 ms 30108 KB Output is correct
3 Correct 12 ms 30040 KB Output is correct
4 Correct 12 ms 30044 KB Output is correct
5 Correct 11 ms 30204 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 30044 KB Output is correct
2 Correct 12 ms 30044 KB Output is correct
3 Correct 12 ms 30040 KB Output is correct
4 Correct 15 ms 30044 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 30300 KB Output is correct
2 Correct 12 ms 30296 KB Output is correct
3 Correct 12 ms 30300 KB Output is correct
4 Correct 13 ms 30300 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31048 KB Output is correct
2 Correct 18 ms 31324 KB Output is correct
3 Correct 15 ms 31068 KB Output is correct
4 Correct 16 ms 31244 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 33116 KB Output is correct
2 Correct 28 ms 34140 KB Output is correct
3 Correct 67 ms 42872 KB Output is correct
4 Correct 29 ms 33880 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 48720 KB Output is correct
2 Correct 59 ms 44372 KB Output is correct
3 Correct 68 ms 46160 KB Output is correct
4 Correct 63 ms 46672 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 51268 KB Output is correct
2 Correct 85 ms 51968 KB Output is correct
3 Correct 116 ms 54456 KB Output is correct
4 Correct 78 ms 49232 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 55516 KB Output is correct
2 Correct 127 ms 55648 KB Output is correct
3 Correct 110 ms 59820 KB Output is correct
4 Correct 106 ms 59988 KB Output is correct

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 116 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 148 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 145 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -