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

struct drzewo_licznikowe {
	drzewo_licznikowe() {
		for (int i = 0; i < (1 << 21); i++) {
			tree[i] = 0;
		}
	}
	long long tree[1 << 21], base = (1 << 20) - 1;

	void add(int curr) {
		curr += base;
		do {
			tree[curr]++;
		} while (curr /= 2);
	}

	long long query(int left, int right) {
		long long res = 0;
		left += base;
		right += base;
		do {
			res += left % 2 == 1 ? tree[left - 1] : 0;
		} while (left /= 2);
		do {
			res += right % 2 == 0 ? tree[right + 1] : 0;
		} while (right /= 2);
		return tree[1] - res;
	}
} tree;

#define NODES_NUMBER 100

long long n, a, b, arr[1003][7], ans;

int main() {
	n = GetN(), a = MyNodeId() * 1000000, b = (MyNodeId() + 1) * 1000000;
	for (int i = a, x; i < b && i < n; i++) {
		x = GetElement(i);
		tree.add(x);
		ans += tree.query(x + 1, tree.base);
	}
	if (MyNodeId() != NODES_NUMBER - 1) {
		for (int i = 2; i <= 5; i++) {
			PutLL(NODES_NUMBER - 1, tree.tree[tree.base + i]);
		}
		PutLL(NODES_NUMBER - 1, ans);
		Send(NODES_NUMBER - 1);
		return 0;
	} else {
		for (int node = 0; node < NODES_NUMBER - 1; node++) {
			Receive(node);
			for (int i = 2; i <= 5; i++) {
				arr[node][i] = GetLL(node);
			}
			ans += GetLL(node);
		}
		for (int i = 1; i < NODES_NUMBER; i++) {
			for (int x = 1; x <= 4; x++) {
				for (int y = x + 1; y <= 5; y++) {
					ans += arr[i][x] * arr[i - 1][y];
				}
			}
			for (int x = 1; x <= 5; x++) {
				arr[i][x] += arr[i - 1][x];
			}
		}
		cout << ans;
		return 0;
	}
}