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

using namespace std;
const int M = 1000000;
const int size = 1<<21;
const int mod = 1<<20;

struct IntTree{
	vector<long long> tab;
	vector<int> left;
	vector<int> right;
	IntTree(vector<long long>& init){
		tab = vector<long long>(size, 0);
		left = vector<int>(size, 0);
		right = vector<int>(size, 0);
		for(int i = 0; i < (int)init.size(); i++){
			tab[mod + i] = init[i];
		}
		for(int i = 0; i < mod; i++){
			left[mod + i] = i;
			right[mod + i] = i;
		}
		for(int i = mod-1; i >= 1; i--){
			tab[i] = tab[i*2] + tab[i*2+1];
			left[i] = left[i*2];
			right[i] = right[i*2+1];
		}
	}
	void add(int where, long long val){
		int act = where + mod;
		while(act >= 1){
			tab[act] += val;
			act /= 2;
		}
	}
	long long get_sum(int beg, int end, int node){
		if(beg > right[node]) return 0;
		if(end < left[node]) return 0;
		if(left[node] >= beg && right[node] <= end) return tab[node];
		return get_sum(beg, end, 2*node) + get_sum(beg, end, 2*node + 1);
	}
};


int main() {
	int n = GetN();
	int number_of_nodes = NumberOfNodes();
	int size_of_interval = n/number_of_nodes;
	int my_node = MyNodeId();
	int beg = my_node * size_of_interval;
	int end = (my_node + 1) * size_of_interval;
	if(my_node == number_of_nodes-1){
		end = n;
	}
	vector<int> tab(M+1,0);
	for(int i = end; i < n; i++){
		tab[GetElement(i)]++;
	}
	vector<long long> amount_infront(M+1, 0);
	for(int i = 0; i <= M; i++){
		amount_infront[i] = tab[i];
	}
	
	long long result = 0;
	IntTree t = IntTree(amount_infront);
	for(int i = end - 1; i >= beg; i--){
		int x = GetElement(i);
		long long x_inverses = t.get_sum(0, x-1, 1);
		result += x_inverses;
		t.add(x, 1);
	}
	if(my_node > 0){
		PutLL(0, result);
		Send(0);
	}
	if(my_node == 0){
		for(int i = 1; i < number_of_nodes; i++){
			Receive(i);
			result += GetLL(i);
		}
		cout<<result<<endl;
	}
	return 0;
}