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
#include "teatr.h"
#include "message.h"
#include <cstdio>
#include <map>
#include <utility>

long long int sortAndCount(std::map<int, int>& quantities, int start, int end)
{
	long long result = 0;
	int k;

	for (int i = start; i < end; ++i) {
		k = GetElement(i);
		for (auto it = quantities.rbegin(); it != quantities.rend() && it->first > k; ++it) {
			result += it->second;
		}
		quantities[k] += 1;
	}
	return result;
}

long long int mergeLocalToTotal(std::map<int, int>& total, std::map<int, int>& local)
{
	long long int result = 0;
	std::map<int, int>::iterator itT = total.begin();
	std::map<int, int>::iterator itL = local.begin();

	long long int totalSum = 0;
	while (itL != local.end()) {
		while (itT != total.end() && itL->first > itT->first) {
			totalSum += itT->second;
			itT++;
		}
		result += totalSum * itL->second;
		itL++;
	}

	for (itL = local.begin(); itL != local.end(); ++itL) {
		total[itL->first] += itL->second;
	}

	return result;
}

int main()
{
	long long result = 0;
	int id = MyNodeId();
	int nodesCnt = NumberOfNodes();
	int n = GetN();
	
	if (n > 1000000) {
		std::map<int, int> quantities;
		int start = (n / nodesCnt) * id;
		int end = (id < nodesCnt - 1) ? (n / nodesCnt) * (id + 1) : n;
		result = sortAndCount(quantities, start, end);

		if (id == 0) {
			std::map<int, int> quantitiesTotal;

			for (int i = nodesCnt - 1; i > 0; ++i) {
				Receive(i);
				result += GetLL(i);
				int t = GetInt(i);
				std::map<int, int> quantitiesLocal;
				for (int j = 0; j < t; ++i) {
					quantitiesLocal.insert(std::make_pair(GetInt(i), GetInt(i)));
				}
				result += mergeLocalToTotal(quantitiesTotal, quantitiesLocal);
			}

			result += mergeLocalToTotal(quantitiesTotal, quantities);
		}
		else {
			PutLL(0, result);
			int t = quantities.size() < 998 ? quantities.size() : 998;
			PutInt(0, t);

			std::map<int, int>::iterator it;
			int i;
			for (it = quantities.begin(), i = 0; i < t && it != quantities.end(); ++i, ++it) {
				PutInt(0, it->first);
				PutInt(0, it->second);
			}
			Send(0);
		}
	}
	else {
		if (id == 0) {
			std::map<int, int> quantities;
			result = sortAndCount(quantities, 0, n);
		}
	}

	if (id == 0) {
		printf("%lld\n", result);
	}

	return 0;
}