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
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include "message.h"
#include "teatr.h"

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

void send_int(int node, int val) { PutInt(node, val); Send(node); };
void send_long(int node, LL val) { PutLL(node, val); Send(node); };
void send_vector_int(int node, const vector<int>& val) { PutLL(node, val.size()); for (LL i = 0; i < val.size(); ++i) { PutInt(node, val[i]); } Send(node); };

int receive_int(int node) { Receive(node); return GetInt(node); };
LL receive_long(int node) { Receive(node); return GetLL(node); };
vector<int> receive_vector_int(int node) { vector<int> res; Receive(node); LL size = GetLL(node); for (LL i = 0; i < size; ++i) { res.push_back(GetInt(node)); } return res; };

void send_partial_max_k(int start, int end)
{
	int res = 0;

	for (int i = start; i < end; ++i)
	{
		res = max(res, GetElement(i));
	}

	send_int(0, res);
}

int calculate_max_k(int NODE, int NNODES)
{
	int res = 0;

	if (NODE == 0)
	{
		for (int node = 0; node < NNODES; ++node)
		{
			res = max(res, receive_int(node));
		}

		for (int node = 1; node < NNODES; ++node)
		{
			send_int(node, res);
		}
	}
	else
	{
		res = receive_int(0);
	}

	return res;
}

void solve_local(int start, int end, int max_k, int NODE, int NNODES)
{
	vector<int> cnt(max_k + 1, 0);

	for (int i = start; i < end; ++i)
	{
		cnt[GetElement(i)]++;
	}

	vector<int> prev_cnt(max_k + 1, 0);

	if (NODE > 0)
	{
		prev_cnt = receive_vector_int(NODE - 1);

		for (int i = 0; i < prev_cnt.size(); ++i)
		{
			cnt[i] += prev_cnt[i];
		}
	}

	if (NODE < NNODES - 1)
		send_vector_int(NODE + 1, cnt);

	LL res = 0;

	for (int i = start; i < end; ++i)
	{
		int x = GetElement(i);

		for (int j = x + 1; j < prev_cnt.size(); ++j)
		{
			res += prev_cnt[j];
		}

		prev_cnt[x]++;
	}

	send_long(0, res);
}

void solve_global(int NNODES)
{
	LL res = 0;

	for (int i = 0; i < NNODES; ++i)
	{
		res += receive_long(i);
	}

	cout << res << endl;
}

int main()
{
	int NNODES = NumberOfNodes();
	int NODE = MyNodeId();
	int N = GetN();

	if (NNODES > N)
		NNODES = N;

	if (NODE >= NNODES)
		return 0;

	int start = (LL)N * NODE / NNODES;
	int end = (LL)N * (NODE + 1) / NNODES;

	send_partial_max_k(start, end);
	int max_k = calculate_max_k(NODE, NNODES);	
	solve_local(start, end, max_k, NODE, NNODES);

	if (NODE == 0)
		solve_global(NNODES);
}