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

using namespace std;

long long n;
long long wynik;

const int R = 1048576;
int drzewo[2*R];
long long sumySuf[1000 * 1000 + 2];
long long zliczone[1000 * 1000 + 2];

void update(int x) {
	x += R;
	drzewo[x]++;

	while(x > 1) {
		x /= 2;
		drzewo[x] = drzewo[2*x] + drzewo[2*x + 1];
	}
}

long long query(int x) {
	int a = x + R;
	int b = 1000 * 1000 + R + 100;
	long long w = drzewo[a];

	if(a != b)
		w += drzewo[b];

	while(a / 2 != b / 2) {
		if(a % 2 == 0)
			w += drzewo[a + 1];
		if(b % 2 == 1)
			w += drzewo[b - 1];

		a /= 2;
		b /= 2;
	}

	return w;
}

void aktualizujSumy() {
	for(int i = 1000 * 1000; i > 0; i--) {
		sumySuf[i] = sumySuf[i + 1] + zliczone[i];
	}
}

void dodajISprawdz(int x) {
	aktualizujSumy();
	for(int i = n * x / NumberOfNodes(); i < n * (x + 1) / NumberOfNodes(); i++) {
		int t = GetElement(i);
		wynik += sumySuf[t + 1];
		zliczone[t]++;
	}
}


void dodajBezSprawdzania(int x) {
	aktualizujSumy();
	for(int i = n * x / NumberOfNodes(); i < n * (x + 1) / NumberOfNodes(); i++) {
		int t = GetElement(i);
		zliczone[t]++;
	}
}

void sprawdzBezDodawania(int x) {
	aktualizujSumy();
	for(int i = n * x / NumberOfNodes(); i < n * (x + 1) / NumberOfNodes(); i++) {
		int t = GetElement(i);
		wynik += sumySuf[t + 1];
	}
}

int main()
{
	n = GetN();

	for(int i = n * MyNodeId() / NumberOfNodes(); i < n * (MyNodeId() + 1) / NumberOfNodes(); i++) {
		int t = GetElement(i);
		wynik += query(t + 1);
		update(t);
		zliczone[t]++;
	}

	if(MyNodeId() % 10 == 0) {
		for(int i = MyNodeId() + 1; i < MyNodeId() + 10; i++) {
			dodajISprawdz(i);
		}
	}
	else {
		for(int i = (MyNodeId() / 10) * 10; i < (MyNodeId() / 10) * 10 + 10; i++) {
			if(i == MyNodeId())
				continue;
			dodajBezSprawdzania(i);
		}
	}

	for(int i = MyNodeId() + 10; i < 100; i += 10) {
		sprawdzBezDodawania(i);
	}

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

    return 0;
}