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
#include "message.h"
#include "teatr.h"
#include <cstdio>
const int MAXVAL = 1000001, BLOCKS = 13;
long long res;
int cnt[MAXVAL], sufsum[MAXVAL+1], tree[MAXVAL], first[100], second[100], beg[BLOCKS+1], end[BLOCKS+1];
void inc(int x) {
  while (x > 0) {
    tree[x]++;
    x -= x&(-x);
  }
}
int get(int x) {
  int res = 0;
  while (x < MAXVAL) {
    res += tree[x];
    x += x&(-x);
  }
  return res;
}
int main() {
  int node = MyNodeId();
  int n = GetN();
  int block_size = (n + BLOCKS - 1) / BLOCKS;
  int nodes = BLOCKS * (BLOCKS + 1) / 2 + 1;
  if (node >= nodes) return 0;

  for (int i=1; i<=BLOCKS; i++) {
    beg[i] = block_size * (i-1);
    end[i] = block_size * i;
    if (end[i] > n) end[i] = n;
  }
  
  {
    int cnt = 0;
    for (int i=1; i<=BLOCKS; i++) {
      for (int j=i+1; j<=BLOCKS; j++) {
        first[cnt] = i;
        second[cnt] = j;
        cnt++;
      }
    }
  }

  if (node == 0) {
    for (int i=1; i<nodes; i++) res += GetLL(Receive(-1));
    printf("%lld\n", res);
    return 0;
  }
  if (node <= BLOCKS) {
    for (int i=beg[node]; i<end[node]; i++) {
      int x = GetElement(i);
      res += get(x+1);
      inc(x);
    }
  } else {
    node -= BLOCKS+1;
    for (int i=beg[first[node]]; i<end[first[node]]; i++) cnt[GetElement(i)]++;
    for (int i=MAXVAL-1; i>0; i--) sufsum[i] = sufsum[i+1] + cnt[i];
    for (int i=beg[second[node]]; i<end[second[node]]; i++) res += sufsum[GetElement(i)+1];
  }
  PutLL(0, res);
  Send(0);
  return 0;
}