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
#include "message.h"
#include "teatr.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#ifdef FANCY_TOOLKIT
  #define main run
#endif

using namespace std;
using namespace __gnu_pbds;


typedef tree<
     pair<int, int>,
     null_type,
     less<pair<int, int>>,
     rb_tree_tag,
     tree_order_statistics_node_update>
  Tree;


int64_t count(int n, int p0, int p1) {
  if(p1 < p0) return 0;
  
  Tree tr;
  int z = 0;
  int64_t ans = 0;
  
  for(int i = p1; i >= p0; i--) {
    int v = GetElement(i);
    ans += tr.order_of_key(make_pair(v, 0));
    tr.insert(make_pair(v, z++));
  }
  
  for(int i = p0 - 1; i >= 0; i--) {
    int v = GetElement(i);
    ans += tr.order_of_key(make_pair(v, 0));
  }
  
  return ans;
}


pair<int, int> partBounds(int parts, int n, int p) {
  return make_pair((n * p) / parts, (n * (p + 1)) / parts - 1);
}


int main() {
  int const nodes = NumberOfNodes();
  int const id = MyNodeId();
  int const n = GetN();
  int const parts = nodes * 2;
  
  pair<int, int> pa = partBounds(parts, n, id);
  pair<int, int> pb = partBounds(parts, n, parts - 1 - id);
  
  int64_t ans = 0;
  ans += count(n, pa.first, pa.second);
  ans += count(n, pb.first, pb.second);
  
  PutLL(0, ans);
  Send(0);

  if(id != 0) return 0;

  int answer = 0;

  for(int i = 0; i < nodes; ++i) {
    Receive(i);
    answer += GetLL(i);
  }

  cout << answer << endl;
  
  return 0;
}


#ifdef FANCY_TOOLKIT
  #undef main
#endif