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
120
121
122
123
124
125
126
// Jedna instancja wypisuje maksymalny wzrost.

#include "message.h"
#include "teatr.h"
#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

#define PB push_back
#define ST first
#define ND second

#define INF 1e8

#define Z 1000000

mt19937 gen;

int r(int a, int b)
{
	uniform_int_distribution<> d(a, b);
	return d(gen);
}

ll res;

void merge(int le, int mid, int ri, vector<int> &v)
{
	vector<int> g;
	int i=le, j=mid+1;
	while(i <= mid && j <= ri)
	{
		if(v[i] <= v[j])
		{
			g.PB(v[i++]);
		}
		else
		{
			g.PB(v[j++]);
			res+=ll(mid-i+1);
		}
	}
	while(i <= mid)
		g.PB(v[i++]);
	while(j <= ri)
		g.PB(v[j++]);
	i=le;
	for(int b : g)
	{
		v[i++] = b;
	}
}

void mergeSort(int le, int ri, vector<int> &v)
{
	if(le>=ri)
		return;
	int mid = (le+ri)/2;
	mergeSort(le, mid, v);
	mergeSort(mid+1, ri, v);
	merge(le, mid, ri, v);
}

int main()
{
	int n = GetN();
	int d = NumberOfNodes();
	int id = MyNodeId();
	vector<pii> g;
	gen.seed(13);
	int t=Z;
	while(t--)
	{
		int i = r(0, n-1);
		int a = GetElement(i);
		g.PB({a, i});
	}
	sort(g.begin(), g.end());
	int s = Z/d;
	pii b, e;
	if(id == 0)
		b = {0, 0};
	else
		b = g[s*id];
	if(id == d-1)
		e = {INF, INF};
	else
		e = g[s*(id+1)];
	res=0;
	ll x=0, y=0;
	vector<int> v;
	for(int i=0; i < n; i++)
	{
		int a = GetElement(i);
		if(a > e.ST)
			x++;
		else if(a == e.ST && i >= e.ND)
			y++;
		else if(a > b.ST || (a == b.ST && i >= b.ND))
		{
			v.PB(a);
			if(a < e.ST)
				res+=x+y;
			else if(a == e.ST)
				res+=x;
		}
	}
	//~ cerr << v.size() << "\n";
	mergeSort(0, v.size()-1, v);
	if(id > 0)
	{
		PutLL(0, res);
		Send(0);
	}
	else
	{
		for(int i=1; i < d; i++)
		{
			Receive(i);
			res+=GetLL(i);
		}
		cout << res << "\n";
	}
}