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

using namespace std;
const int M = 1000010;
vector<int> fen(M + 1);
int n;

void add(int x) {
	for ( ; x <= M; x += x & -x) fen[x]++;
}
long long read(int x) {
	long long res = 0;
	for ( ; x >= 1; x -= x & -x) res += fen[x];
	return res;
}
long long get(int pocz, int kon) {
	if (pocz > kon) return 0;
	return read(kon) - read(pocz - 1);
}
int main() {
	int id = MyNodeId(), v;
	long long ans = 0;
	n = GetN();
	int nodes = NumberOfNodes();
	if (nodes > n) {
		if (id) return 0;
		fen.resize(n + 1);
		for (int a = 0; a < n; a++) {
			v = GetElement(a);
			ans += get(v + 1, M);
			add(v);
		}
		cout << ans << endl;
	}
	else {
		int len = n / nodes;
		int pocz, kon;
		pocz = id * len;
		if (id == nodes - 1) kon = n;
		else kon = pocz + len;
		vector<int> tab;
		for (int a = pocz; a < kon; a++) {
			v = GetElement(a);
			ans += get(v + 1, M);
			add(v);
			tab.push_back(v);
		}
		vector<long long> cnt(M + 1);
		for (int a = 0; a < pocz; a++) {
			v = GetElement(a);
			cnt[v]++;
		}
		for (int a = 1; a <= M; a++) {
			cnt[a] += cnt[a - 1];
		}
		for (int a = pocz; a < kon; a++) {
			ans += cnt[M] - cnt[tab[a - pocz]];
		}
		long long value = 0;
		if (id) {
			Receive(id - 1);
			value = GetLL(id - 1);
		}
		value += ans;
		if (id != nodes - 1) {
			PutLL(id + 1, value);
			Send(id + 1);
		}
		else {
			cout << value << endl;
		}
	}
	 

    return 0;
}