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
#include <iostream>

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

using namespace std;

typedef unsigned long long ull;

const int COORDINATOR_ID = 0;
const int NODES_COUNT = 100;
const int MAX_INPUT_SIZE = 100 * 1000 * 1000;
const int ONE_CHUNK_SIZE = MAX_INPUT_SIZE / NODES_COUNT;

const int VALUES_COUNT = 1 << 20;
const int HISTOGRAM_TREE_SIZE = 2 * VALUES_COUNT;
const int HISTOGRAM_BEGIN = VALUES_COUNT;
const int HISTOGRAM_END = 2 * VALUES_COUNT;

long long histogram_tree[HISTOGRAM_TREE_SIZE] = { 0 };

inline void histogram_add(int value) {
	++histogram_tree[HISTOGRAM_BEGIN + value];
}

inline void histogram_tree_build() {
	int iteration_start = HISTOGRAM_BEGIN / 2;
	int iteration_end = HISTOGRAM_BEGIN;

	while (iteration_start != 0) {
		for (int i = iteration_start; i < iteration_end; ++i) {
			histogram_tree[i] = histogram_tree[2 * i] + histogram_tree[2 * i + 1];
		}

		iteration_start /= 2;
		iteration_end /= 2;
	}
}

inline long long histogram_tree_add(int value) {
	int pos = HISTOGRAM_BEGIN + value;
	long long result = histogram_tree[1] - histogram_tree[pos];

	while (pos != 1) {
		if (pos % 2 == 1) {
			result -= histogram_tree[pos - 1];
		}
		++histogram_tree[pos];
		pos /= 2;
	}
	++histogram_tree[1];

	return result;
}

inline long long sub_solve(int instance_number) {
	int pre_start = 0;
	int proc_start = instance_number * ONE_CHUNK_SIZE;
	int proc_end = (instance_number + 1) * ONE_CHUNK_SIZE;
	int pre_end = instance_number == 0 ? 0 : proc_start;
	long long result = 0;

	int problem_size = GetN();

	if (proc_start >= problem_size) {
		return result;
	}
	if (proc_end > problem_size) {
		proc_end = problem_size;
	}

	for (int i = pre_start; i < pre_end; ++i) {
		histogram_add(GetElement(i));
	}

	histogram_tree_build();

	for (int i = proc_start; i < proc_end; ++i) {
		result += histogram_tree_add(GetElement(i));
	}

	return result;
}

inline void gather_results(long long result) {
	ull accumulated_result = result;

	for (int i = 1; i < NODES_COUNT; ++i) {
		Receive(i);
		accumulated_result += GetLL(i);
	}

	cout << accumulated_result << endl;
}

inline void sent_result(long long result) {
	PutLL(COORDINATOR_ID, result);
	Send(COORDINATOR_ID);
}

inline void solve() {
	int instance_number = MyNodeId();
	long long result = sub_solve(instance_number);

	if (instance_number == COORDINATOR_ID) {
		gather_results(result);
	} else {
		sent_result(result);
	}
}

int main() {
	ios_base::sync_with_stdio(0);

	solve();

	return 0;
}