Submission #1121027

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1121027	2024-11-28T10:34:38 Z	chuyenluaga	Tree Rotations (POI11_rot)	C++17	100 / 100	548 ms	32328 KB

// 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;
map<int,Tree<int> > s;
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()) s[s1].swap(s[s2]);
	s[s1].swap(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.erase(s1);
    s.erase(s2);
	//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(0);
	cout << ans;
}

Subtask #1
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct

Subtask #2
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	508 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	456 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	336 KB	Output is correct
2	Correct	2 ms	516 KB	Output is correct
3	Correct	3 ms	592 KB	Output is correct
4	Correct	2 ms	592 KB	Output is correct

Subtask #4
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	1104 KB	Output is correct
2	Correct	6 ms	700 KB	Output is correct
3	Correct	7 ms	1104 KB	Output is correct
4	Correct	4 ms	1360 KB	Output is correct

Subtask #5
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	3096 KB	Output is correct
2	Correct	18 ms	1104 KB	Output is correct
3	Correct	59 ms	2668 KB	Output is correct
4	Correct	14 ms	2608 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	97 ms	3988 KB	Output is correct
2	Correct	64 ms	7496 KB	Output is correct
3	Correct	87 ms	9896 KB	Output is correct
4	Correct	88 ms	9752 KB	Output is correct

Subtask #7
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	132 ms	20296 KB	Output is correct
2	Correct	123 ms	14496 KB	Output is correct
3	Correct	176 ms	8496 KB	Output is correct
4	Correct	112 ms	6984 KB	Output is correct

Subtask #8
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	149 ms	7752 KB	Output is correct
2	Correct	170 ms	10524 KB	Output is correct
3	Correct	171 ms	20352 KB	Output is correct
4	Correct	175 ms	19832 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	327 ms	19540 KB	Output is correct
2	Correct	282 ms	13640 KB	Output is correct
3	Correct	263 ms	16600 KB	Output is correct
4	Correct	280 ms	14920 KB	Output is correct
5	Correct	431 ms	13128 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	283 ms	16136 KB	Output is correct
2	Correct	311 ms	30552 KB	Output is correct
3	Correct	379 ms	21320 KB	Output is correct
4	Correct	245 ms	32328 KB	Output is correct
5	Correct	548 ms	15432 KB	Output is correct

Subtask #11
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	382 ms	19148 KB	Output is correct
2	Correct	355 ms	16156 KB	Output is correct
3	Correct	385 ms	12520 KB	Output is correct
4	Correct	370 ms	19016 KB	Output is correct
5	Correct	386 ms	28744 KB	Output is correct
6	Correct	445 ms	16064 KB	Output is correct

Submission #1121027

Compilation message