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
// Jedna instancja wypisuje maksymalny wzrost.

#include "message.h"
#include "bits/stdc++.h"
#include <chrono>

#include "teatr.h"

struct Timer {
    Timer() {
      start = std::chrono::high_resolution_clock::now();
    }

    double elapsed() {
      return std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1> >>
        (std::chrono::high_resolution_clock::now() - start).count();
    }

    std::chrono::time_point<std::chrono::high_resolution_clock> start;
};

using namespace std;

using ll = long long;

ll inversions(vector<int>& A) {
  if (A.size() <= 1) return 0;

  ll res = 0;

  int mid = A.size() / 2;
  vector<int> A1 (A.begin(), A.begin() + mid);
  vector<int> A2 (A.begin() + mid, A.end());
  res += inversions(A1);
  res += inversions(A2);

  int ind = 0;

  for (int i=0; i < A1.size(); i++) {
    while (ind < A2.size() && A1[i] > A2[ind]) ind ++;
    res += ind;
  }

  merge(A1.begin(), A1.end(), A2.begin(), A2.end(), A.begin());

  return res;
}

int main() {
  int nodes = NumberOfNodes();
  int id = MyNodeId();
  int n = GetN();

  //Timer t;

  int slice = (n + nodes - 1) / nodes;

  int maxi = 0;
  const int MAX = 1000 * 1000;

  int begin = slice * id;
  int end = min(slice * (id + 1), n);

  vector<int> counts (MAX);
  for(int i=end; i<n; i++) {
    counts[GetElement(i)] ++;
  }

  vector<int> prefix_counts (MAX+1);
  for (int i=0; i<MAX; i ++) {
    prefix_counts[i+1] = prefix_counts[i] + counts[i];
  }

  long long res = 0;

  vector<int> inside;
  for(int i=begin; i<end; i++) {
    int v = GetElement(i);
    inside.push_back(v);
    res += prefix_counts[v];
  }

  res += inversions(inside);

  PutLL(0, res);
  Send(0);
  //cerr << int(t.elapsed() * 1000) << " ms" << endl;

  if (id != 0) return 0;

  ll res2 = 0;
  for (int i=0; i < nodes; i ++) {
    Receive(i);
    res2 += GetLL(i);
  }
  cout << res2 << endl;
}