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
#include <iostream>
#include <vector>

#include "message.h"
#include "teatr.h"

using namespace std;

unsigned long long merge(vector<int>& v, int lo, int pivot, int hi) {
  unsigned long long res = 0;
  int i = lo, j = pivot + 1, k = 0;
  vector<int> tmp;
  tmp.resize(hi - lo + 1);

  while (i <= pivot && j <= hi) {
    if (v[i] <= v[j]) {
      tmp[k] = v[i];
      ++i;
    } else {
      tmp[k] = v[j];
      res += pivot - i + 1;
      ++j;
    }
    ++k;
  }
  while (i <= pivot) {
    tmp[k] = v[i];
    ++i;
    ++k;
  }
  while (j <= hi) {
    tmp[k] = v[j];
    ++j;
    ++k;
  }

  for (int i = lo; i <= hi; ++i) {
    v[i] = tmp[i - lo];
  }

  return res;
}

unsigned long long mergeSort(int n, vector<int>& v) {
  unsigned long long res = 0;
  for (int range = 1; range <= n - 1; range = 2 * range) {
    for (int lo = 0; lo + range - 1 < n - 1; lo += 2 * range) {
      int mid = lo + range - 1;
      int hi = min(lo + 2 * range - 1, n - 1);
      res += merge(v, lo, mid, hi);
    }
  }
  return res;
}

int main(int argc, char const *argv[]) {

  if(MyNodeId() != 0) return 0;
  int n = GetN();
  vector<int> v;
  v.resize(n);
  for(int i = 0; i < n; ++i) {
    v[i] = GetElement(i);
  }

  cout << mergeSort(n, v) << endl;

  return 0;
}