Submission #1120993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120993		chuyenluaga	Untitled (POI11_rot)	C++17	36 / 100	1067 ms	65536 KiB

Main

// Source: https://oj.uz/problem/view/POI11_rot
// State: Writing...

#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
#include <ios>
using namespace std;
using namespace __gnu_pbds;

//#define int long long
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;


long long ans = 0;
Tree<int> s[200001];
int timedfs = 1;


void solve(int id){
	int x;
//	Tree<int> s1,s2;
	cin >> x;
	if (x != 0){
		s[id].insert(x);
		return;
	}
	int s1 = ++timedfs;
	solve(s1);
	int s2 = ++timedfs;
	solve(s2);
	if (s[s1].size() < s[s2].size()) swap(s[s1], s[s2]);
	swap(s[s1],s[id]);
	//auto i1 = s1.begin(), i2 = s2.begin();
	long long nghich = 0;
	for (int v : s[s2])
		nghich = nghich + s[id].order_of_key(v);
	
	ans = ans + min((long long)nghich,(long long)s[id].size()*(long long)s[s2].size() - nghich);
	//cout << ans << endl;

	for (int v : s[s2]){
		s[id].insert(v);
	}
	//s[s1].clear();
	//s[s2].clear();
	//swap(s[id],s[s1]);
	return;
}


int32_t main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(NULL);cout.tie(NULL);
	int n;
	cin >> n;
	solve(1);
	cout << ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10