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
#include "message.h"
#include <bits/stdc++.h>
#include "teatr.h"

using namespace std;

const int N = 1000 * 1000 + 10;
const int MAXN = 1000 * 1000;
const int rozmiar = 1 << 20;
int war_pop[N];
int war_akt[N];
int d_p[2 * rozmiar];

void dodaj(int v) {
	v += rozmiar;
	while (v > 0) {
		d_p[v]++;
		v /= 2;
	}
}

long long suma (int pocz, int kon) {
	pocz += rozmiar;
	kon += rozmiar;
	long long wynik = d_p[pocz];
	if (pocz != kon)
		wynik += d_p[kon];

	while (pocz / 2 != kon / 2) {
		if (pocz % 2 == 0)
			wynik += d_p[pocz + 1];
		if (kon % 2 == 1)
			wynik += d_p[kon - 1];
		
		pocz /= 2;
		kon /= 2;	
	}
	return wynik;
}

long long count_inversion(int pocz, int kon) {
	long long wynik = 0;
	int wzrost;
	for (int i = pocz; i <= kon; i++) {
		wzrost = GetElement(i);
		wynik += suma(wzrost + 1, rozmiar - 1);
		dodaj(wzrost);
	}
	return wynik;
}

int main() {
	int n = GetN(), node_id = MyNodeId(), instance_number = NumberOfNodes();
	
	long long wynik = 0;
	if (n <= 200) {
		if (node_id == 0)
			cout << count_inversion(0, n -1);
		return 0;	
	}

	if (node_id == 0) {
		int przedzial = n / instance_number;
			
		for (int i = 0; i < n; i++) {
			war_akt[GetElement(i)]++;
			if ((i + 1) % przedzial == 0 && i < (instance_number - 2) * przedzial) {
				//cout << i << "\n";				
				long long suma_przed = 0;
				
				for (int j = 1; j <= MAXN; j++) {
					wynik += (long long)war_akt[MAXN - j + 1] * suma_przed;
					suma_przed += (long long)war_pop[MAXN - j + 1];
				}
				for (int j = 0; j < N; j++) {
					war_pop[j] += war_akt[j];
					war_akt[j] = 0;				
				}
								
			}
			
		}
		long long suma_przed = 0;

		for (int j = 1; j <= MAXN; j++) {
			wynik += (long long)war_akt[MAXN - j + 1] * suma_przed;
			suma_przed += (long long)war_pop[MAXN - j + 1];
		}
		
		for (int i = 1; i < instance_number; i++) {
			Receive(i);			
			wynik += GetLL(i);
		}
	
		cout << wynik << "\n";
	} else {
		int przedzial = n / instance_number;
		int pocz = 	(node_id - 1) * przedzial;
		int kon = (node_id - 1) * przedzial + przedzial - 1;
		if (node_id == instance_number - 1)
			kon = n - 1;
 
		//cout << przedzial << " " << pocz << " " << kon << "\n";
		PutLL(0, count_inversion(pocz, kon));
		Send(0);
	}
}