Submission #1115152

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115152		VectorLi	Untitled (POI11_rot)	C++17	72 / 100	252 ms	65536 KiB

Main

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10