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<bits/stdc++.h>
#include"message.h"
#include"teatr.h"
using namespace std;
typedef long long int lld;

const int SIZE = 1e6;

lld T[SIZE+5];
lld P[SIZE+5];
/*
int GetN(void){
	return 10000000;
} // Odp.: 27499972500000
//         27499982500000

int GetElement(int k){
	return SIZE-k%SIZE;
}
*/
lld MergeSort(int b, int e){
	if(e <= b)
		return 0ll;

	lld res = 0;
	int m = (b+e)/2;
	res += MergeSort(b,m);
	res += MergeSort(m+1,e);

	int x = b;
	int y = m+1;
	for(int i=b;i<=e;i++)
		if(x <= m){
			if(y <= e){
				if(T[x] <= T[y])
					P[i] = T[x++];
				else
					P[i] = T[y++], res += (lld) (m+1-x);
			}else
				P[i] = T[x++];
		}else
			P[i] = T[y++];

	for(int i=b;i<=e;i++)
		T[i] = P[i];

	return res;
}

lld calcInversion(void){
	int nr = MyNodeId();
	int n = GetN();

	int b = nr*SIZE;
	int e = min((nr+1)*SIZE, GetN())-1;

	if(e < b)
		return 0ll;

	lld res = 0ll;

	for(int i=b;i<=e;i++)
		T[i-b] = GetElement(i);

	return MergeSort(0,e-b);
}

int main(void){
	if(MyNodeId() != 0){
		PutLL(0, calcInversion());
		Send(0);
		return 0;
	}

	lld res = calcInversion();

	for(int i=0;i<SIZE+5;i++)
		T[i] = 0;

	for(int i=0;i<NumberOfNodes();i++){
		int b = i*SIZE;
		int e = min((i+1)*SIZE, GetN())-1;

		for(int j=0;j<SIZE+5;j++)
			P[j] = 0;

		for(int j=b;j<=e;j++){
			P[GetElement(j)]++;
			res += T[GetElement(j)+1];
		}

		for(int j=SIZE+1;j>=0;j--){
			P[j] += P[j+1];
			T[j] += P[j];
		}
	}

	for(int i=1;i<100;i++){
		Receive(i);
		res += GetLL(i);
	}
	
	cout << res << "\n";

	return 0;
}