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
#include "message.h"
#include "teatr.h"
#include <iostream>
#include <algorithm>

using namespace std;

int tab[1000000+1024*1024+1] = {0};

int parent(int a)
{
	return (a-1)/2;
}

int left(int a)
{
	return a*2+1;
}

int right(int a)
{
	return a*2+2;
}

int pos(int a)
{
	return a + 1024*1024 - 1;
}

int gethigher(int a)
{
	int level = 1024*1024;
	int fin = pos(a);
	int i = 0;
	int sum = tab[0] - tab[fin];
	int where = 0;
	do {
		int li = left(i);
		int ri = right(i);
		level = level/2;
		int mid = where + level;
		if (a < mid) {
			i = li;
		} else {
			where += level;
			sum -= tab[li];
			i = ri;
		}
	} while (i != fin);
	return sum;
}

void inc(int a)
{
	int i = pos(a);
	tab[i]++;
	while (i != 0) {
		i = parent(i);
		tab[i]++;
	}
}

void build()
{
	int p = pos(1000000);
	for (p = pos(1000000); p > 0; p--) {
		tab[parent(p)] += tab[p];
	}
}

int main()
{
	int start = min(MyNodeId() * 1000000, GetN());
	int end = min((MyNodeId()+1) * 1000000, GetN());

	long long sum = 0;

	if (start < end) {
		for (int i = 0; i < start; i++)
		{
			int a = GetElement(i);
			tab[pos(a)]++;
		}
		build();
	}

	for (int i = start; i < end; i++) {
		int a = GetElement(i);
		sum += gethigher(a);
		inc(a);
	}

	if (MyNodeId() == 0)
	{
		for (int i = 0; i < NumberOfNodes()-1; i++)
		{
			sum += GetLL(Receive(-1));
		}
		cout << sum << endl;
	} else {
		PutLL(0, sum);
		Send(0);
	}

	return 0;
}