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
127
#include "message.h"
#include "teatr.h"
#include <bits/stdc++.h>
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define TRAV(i, a) for(auto &i : a)
#define SZ(i) ((int)(i).size())
#define X first
#define Y second
#define PR std::pair
#define PII std::pair<int, int>
#define MP std::make_pair
#define ll long long
#define VI std::vector<int>
#define LSB(i) ((i) & -(i))

const int MAXH = 1000000;

struct BIT{
	std::vector<int> tab;
	BIT(int size){
		tab.resize(size);
	}
	int sum(int i){
		int sum = 0;
		while (i > 0)
			sum += tab[i], i -= LSB(i);
		return sum;
	}
	void add(int i, int k){
		while (i < SZ(tab))
			tab[i] += k, i += LSB(i);
	}
};
ll count_inversions(const VI &vec){
	ll ret = 0;
	BIT bit(MAXH+1);
	TRAV(a, vec){
		ret += bit.sum(MAXH)-bit.sum(a);
		bit.add(a, 1);
	}
	return ret;
}

ll count_inversions_big(VI &lsum, VI &rpref){
	ll ret = 0;
	REP(i, 1, MAXH+1){
		ret += 1ll*lsum[i]*rpref[i-1];
	}
	return ret;
}

void add_sum(int a, int b, VI &sum){
	REP(i, a, b+1) sum[GetElement(i)]++;
}

void get_sum_pref(int a, int b, VI &sum, VI &pref){
	std::fill(sum.begin(), sum.end(), 0);
	REP(i, a, b+1) sum[GetElement(i)]++;
	pref[0] = 0;
	REP(i, 1, MAXH+1) pref[i] = pref[i-1] + sum[i];
}

ll ans;
int n, NODES, ME;
std::vector<PII> przedz;
VI small;
VI lsum, lpref, rsum, rpref, allsum, nlsum;

int main() {
	n = GetN();
	NODES = NumberOfNodes();
	ME = MyNodeId();

	if(n <= 1000000){
		if(ME != 0) return 0;
		VI A(n);
		FOR(i, n) A[i] = GetElement(i);
		std::printf("%lld", count_inversions(A));
		return 0;
	}

	int place = 0;
	FOR(i, NODES){
		int upto = (i < NODES-1 ? place+n/NODES : n);
		przedz.push_back(MP(place, upto-1));
		place = upto;
	}

	int mywork = przedz[ME].Y-przedz[ME].X+1;
	small.resize(mywork);
	FOR(i, mywork) small[i] = GetElement(przedz[ME].X+i);
	ans += count_inversions(small);
	
	// works only for NODES = 100

	int which = (ME%10)*10;
	lsum.resize(MAXH+1);
	add_sum(przedz[which].X, przedz[which].Y, lsum);
	rsum.resize(MAXH+1);
	rpref.resize(MAXH+1);
	REP(i, 1, 10){
		get_sum_pref(przedz[which+i].X, przedz[which+i].Y, rsum, rpref);
		if(ME < 10) ans += count_inversions_big(lsum, rpref);
		FOR(j, MAXH+1) lsum[j] += rsum[j];
	}

	lpref.resize(MAXH+1);
	REP(i, 1, MAXH+1) lpref[i] = lpref[i-1] + lsum[i];
	nlsum.resize(MAXH+1);
	while(which > 0){
		which -= 10;
		std::fill(nlsum.begin(), nlsum.end(), 0);
		add_sum(przedz[which+ME/10].X, przedz[which+ME/10].Y, nlsum);
		ans += count_inversions_big(nlsum, lpref);
	}
	if(ME == 0){
		REP(i, 1, NODES){
			Receive(i);
			ans += GetLL(i);
		}
		std::printf("%lld", ans);
	}else{
		PutLL(0, ans);
		Send(0);
	}
}