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

const int len = 1000000;
const int p = (1<<20);
int n, i, x, a, b, id;
int suf [1000002];
int tree [p+p];
ll out;

int sum (int l, int r)
	{
	l+=p; r+=p;
	int res = tree[l]+tree[r];
	while (l/2!=r/2)
		{
		if (l%2==0)
			res+=tree[l+1];
		if (r%2==1)
			res+=tree[r-1];
		l/=2; r/=2;
		}
	return res;
	}

void inc (int u){
	for (u+=p; u!=0; u/=2)
		tree[u]++;
	}

int main ()
	{
	id = MyNodeId();
	n = GetN();
	a = len*id;
	b = min(n, a+len);
	if (a>=n)
		return PutLL(0, 0), Send(0), 0;
	for (i=a; i<b; i++)
		{
		x = GetElement(i);
		out += (ll)(sum(x+1, 1000002));
		inc(x);
		}
	for (i=1000000; i>=0; i--)
		suf[i]=suf[i+1]+tree[i+p];
	for (i=b; i<n; i++)
		{
		x = GetElement(i);
		out += (ll)(suf[x+1]);
		}
	if (id!=0)
		return PutLL(0, out), Send(0), 0;
	x = NumberOfNodes()-1;
	while (x--)
		out += GetLL(Receive(-1));
	printf ("%lld\n",out);
	return 0;
	}