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
#include <iostream>
#include <numeric> 
#include "message.h"
#include "teatr.h"
//#include "bits/stdc++.h"

struct Node {
	int data;
	int leftSubTreeSize;
	int dup;
	Node *left, *right;
	Node(int x) {
		data = x;
		leftSubTreeSize = 0; 
		dup = 1;  
		left = right = NULL;
	}
};
Node *insert(Node *root, int key, int *countArray, int index) {
	if (!root)return (new Node(key));
	if (key > root->data) {
		root->right = insert(root->right, key, countArray, index);
		countArray[index] = countArray[index] + root->leftSubTreeSize + root->dup;
	}
	else if (key < root->data) {
		root->left = insert(root->left, key, countArray, index);
		root->leftSubTreeSize += 1;
	}
	else if (key == root->data) {
		root->dup += 1;
		countArray[index] += root->leftSubTreeSize;
	}
	return root;
}
int *countSmaller(int *A, int N) {

	int *countArray = new int[N];
	for (int i = 0; i < N; i++)
		countArray[i] = 0;
	Node *root = NULL;
	for (int i = N - 1; i >= 0; i--)
		root = insert(root, A[i], countArray, i);
	return countArray;
}
long long arraySum(int a[], int n) 
{ 
	long long initial_sum = 0;
	return std::accumulate(a, a + n, initial_sum); 
}

int main()
{
    if (MyNodeId() != 0) return 0;
	int N = GetN();

	int *A = new int[N+1];

	for (int i = 0; i < N; i++)
		A[i]=GetElement(i);

	int *res = countSmaller(A, N);
	std::cout << arraySum(res,N);
	return 0;
}