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
#include <cstdio>
#include <algorithm>
#include "teatr.h"
#include "message.h"
using namespace std;
typedef long long LL;

const int MX = 5;

LL r, c[MX+1];


int main() {
  int me = MyNodeId(), nodes = NumberOfNodes();
  int n = GetN(), len = (n + nodes - 1) / nodes;
  int a = me*len, b = min(n, a+len);
  for (int i=a; i<b; ++i) {
    int x = GetElement(i);
    for (int j=MX; j > x; --j) r += c[j];
    ++c[x];
  }

  if (me) {
    PutLL(0, r);
    for (int i=1; i<=MX; ++i) PutLL(0, c[i]);
    Send(0);
  } else {
    for (int i=1; i<nodes; ++i) {
      Receive(i);
      r += GetLL(i);
      for (int j=1; j<=MX; ++j) {
        LL x = GetLL(i);
        for (int k=MX; k>j; --k) r += c[k] * x;
        c[j] += x;
      }
    }
    printf("%lld\n", r);
  }

  return 0;
}