oj.uz

답안 #1121027

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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