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
#include <cstdio>
#include <algorithm>

#include "message.h"
#include "teatr.h"

typedef long long LL;

int main() {
	int n = GetN();
	int id = MyNodeId();
	int insts = NumberOfNodes();
	int block_size = (n+insts-1)/insts;
	int begin = std::min(n, id*block_size);
	int end = std::min(n, (id+1)*block_size);
	
	int freq_here[6] = {0};
	int freq_then[6] = {0};

	for(int i = begin; i < end; i++)
		freq_here[GetElement(i)]++;

	if(id != 0) {
		Receive(id-1);
		for(int i = 1; i <= 5; i++)
			freq_then[i] = GetInt(id-1);
	}

	if(id != insts-1) {
		for(int i = 1; i <= 5; i++)
			PutInt(id+1, freq_here[i] + freq_then[i]);
		Send(id+1);
	}

	LL ans = 0;

	for(int i = begin; i < end; i++) {
		int k = GetElement(i);
		for(int j = 5; j > k; j--)
			ans += freq_then[j];
		freq_then[k]++;
	}
	
	if(id != 0) {
		PutLL(0, ans);
		Send(0);
	}
	else {
		for(int i = 1; i < insts; i++) {
			Receive(i);
			ans += GetLL(i);
		}
		printf("%lli\n", ans);
	}
}