oj.uz

Submission #1115152

# Submission time Handle Problem Language Result Execution time Memory
1115152 2024-11-20T07:14:47 Z VectorLi Tree Rotations (POI11_rot) C++17
72 / 100
 252 ms 65536 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define I64 long long

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = (int) 2E5;

int n;
int e[N * 2 - 1][2];

int t;
ordered_set<int> s[N * 2 - 1];

int build(int u) {
	int p = t;
	t = t + 1;
	int x;
	cin >> x;
	if (x == 0) {
		e[u][0] = build(t);
		e[u][1] = build(t);
	} else {
		s[u].insert(x);
	}
	return p;
} 

I64 x;

void DFS(int u) {
	if (e[u][0] >= 0) {
		int v[2];
		v[0] = e[u][0];
		v[1] = e[u][1];
		DFS(v[0]);
		DFS(v[1]);
		if (s[v[0]].size() < s[v[1]].size()) {
			s[v[0]].swap(s[v[1]]);
		}
		I64 a = 0, b = 0;
		for (auto x : s[v[1]]) {
			a = a + (int) s[v[0]].order_of_key(x);
			b = b + (int) (s[v[0]].size()) - (int) s[v[0]].order_of_key(x);
		}
		s[u].swap(s[v[0]]);
		x = x + min(a, b);
		for (auto x : s[v[1]]) {
			s[u].insert(x);
		}
	}
}

void solve() {
	cin >> n;
	n = n * 2 - 1;
	for (int i = 0; i < n; i++) {
		e[i][0] = 0 - 1;
		e[i][1] = 0 - 1;
	}
	build(0);
	DFS(0);
	cout << x << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	solve();
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 33628 KB Output is correct
2 Correct 24 ms 33788 KB Output is correct
3 Correct 26 ms 33804 KB Output is correct
4 Correct 27 ms 33616 KB Output is correct
5 Correct 23 ms 33616 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 33872 KB Output is correct
2 Correct 23 ms 33616 KB Output is correct
3 Correct 22 ms 33616 KB Output is correct
4 Correct 25 ms 33800 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 33864 KB Output is correct
2 Correct 26 ms 33872 KB Output is correct
3 Correct 28 ms 33872 KB Output is correct
4 Correct 25 ms 33872 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 34640 KB Output is correct
2 Correct 27 ms 34620 KB Output is correct
3 Correct 25 ms 34640 KB Output is correct
4 Correct 25 ms 34640 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 36176 KB Output is correct
2 Correct 40 ms 36936 KB Output is correct
3 Correct 78 ms 44872 KB Output is correct
4 Correct 41 ms 36944 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 49516 KB Output is correct
2 Correct 78 ms 45896 KB Output is correct
3 Correct 86 ms 47492 KB Output is correct
4 Correct 86 ms 47488 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 52148 KB Output is correct
2 Correct 131 ms 51864 KB Output is correct
3 Correct 152 ms 53832 KB Output is correct
4 Correct 110 ms 48456 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 52896 KB Output is correct
2 Correct 169 ms 53272 KB Output is correct
3 Correct 166 ms 58184 KB Output is correct
4 Correct 169 ms 58316 KB Output is correct

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 195 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 224 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 252 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -