1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
// Grzegorz Bukowiec
// Potyczki Algorytmiczne 2018
// Runda 4B - Teatr

#include <iostream>
#include <algorithm>
#include "message.h"
#include "teatr.h"
using namespace std;

void merge(int* arr, int* arr2, int idx, int idx2, int idx3, long long &result) {
	int i = idx;
	int j = idx2;
	int k = idx;
	while (i < idx2 && j < idx3) {
		if (arr[i] <= arr[j]) {
			arr2[k++] = arr[i++];
		} else {
			arr2[k++] = arr[j++];
			result += (long long)(idx2 - i);
		}
	}
	while (i < idx2) {
		arr2[k++] = arr[i++];
	}
}

void divide(int* arr, int* arr2, int idx, int idx3, long long &result) {
	if (idx + 1 < idx3) {
		int idx2 = (idx + idx3 + 1) / 2;
		divide(arr2, arr, idx, idx2, result);
		divide(arr2, arr, idx2, idx3, result);
		merge(arr, arr2, idx, idx2, idx3, result);
	}
}

int main() {
	int n = GetN();
	int id = MyNodeId();
	
	if (id == 0) {
		long long result = 0;
		
		//subtask
		bool smallN = (n <= 1000);
		bool smallVals = true;
		for (int i = 0; i < n; ++i) {
			if (GetElement(i) > 5) {
				smallVals = false;
				break;
			}
		}
		
		//smallVals
		if (smallVals) {
			int howMany[5] = {0, 0, 0, 0, 0};
			for (int i = 0; i < n; ++i) {
				int a = GetElement(i);
				--a;
				++howMany[a];
				for (int j = a + 1; j < 5; ++j) {
					result += howMany[j];
				}
			}
			cout << result;
		}		
		//brute force
		else if (smallN) {			
			for (int i = 0; i < n; ++i) {
				for (int j = i + 1; j < n; ++j) {
					if (GetElement(i) > GetElement(j)) {
						++result;
					}
				}
			}
			
			cout << result;
		}
		//might be a bug somewhere
		else {
			int *arr = new int[n];
			int *arr2 = new int[n];
			for (int i = 0; i < n; ++i) {
				arr[i] = arr2[i] = GetElement(i);
			}
			
			divide(arr, arr2, 0, n, result);
			cout << result;
			
			delete[] arr;
			delete[] arr2;
		}
	}
	
	return 0;
}