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
#include <iostream>
#include "message.h"
#include "teatr.h"

const int TSIZE = 1<<20;
int tree[2*TSIZE];
int count[1000100];

void treeupdate(int p) {
	for (p += TSIZE; p; p>>=1) {
		tree[p]++;
	}
}

int treeget(int p, int k) {
	int m = 0;
	p += TSIZE;
	k += TSIZE;
	while (p < k) {
		if (p & 1) m+=tree[p++];
		if (!(k & 1)) m+=tree[k--];
		p >>= 1;
		k >>= 1;
	}
	if (p==k) m+=tree[p];
	return m;
}

int main() {
	int N = GetN();
	int begin = (long long int)MyNodeId() * N / NumberOfNodes();
	int end = (long long int)(MyNodeId()+1) * N / NumberOfNodes();
	long long int result = 0;

	for (int i=0; i<begin; ++i) {
		count[GetElement(i)]++;
	}

	for (int i=1000000; i>=0; --i) {
		count[i] += count[i+1];
	}

	for (int i=begin; i<end; ++i) {
		result += count[GetElement(i)+1];
		result += treeget(GetElement(i)+1, TSIZE-1);
		treeupdate(GetElement(i));
	}

	if (MyNodeId() != 0) {
		PutLL(0, result);
		Send(0);
	} else {
		for (int i=1; i<NumberOfNodes(); ++i) {
			Receive(i);
			result += GetLL(i);
		}
		std::cout << result << std::endl;
	}
	return 0;
}