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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include "message.h"
#include "teatr.h"
#include "bits/stdc++.h"

using namespace std;

#define MAX_N = 1000*1000+2;

int period = 1000*1000+2;

bool deb = 0;

int size = 0;
int smallerThan[6];
int nums[6];
long long arr[1000006];
long long helpTab[1000006];
long long counter = 0;
long long result = 0;

void merge(int b, int mid, int e){
  int i = b;
  int j = mid+1;
  int k = b;
  for(int c = i; c <= e; c++){
    helpTab[c] = arr[c];
  }
  while(i <= mid && j <= e){
    if(helpTab[i] < helpTab[j]){
      arr[k] = helpTab[j];
      j++;
      k++;
      continue;
    }
    if(helpTab[i] > helpTab[j]){
      counter+=(k-i);
      arr[k] = helpTab[i];
      i++;
      k++;
      continue;
    }
    if(helpTab[i] == helpTab[j]){
      counter+=(k-i);
      arr[k] = helpTab[i];
      i++;
      k++;
      continue;
    }
  }

  for(int o = i; o <= mid; o++){
    counter+=(k-o);
    arr[k] = helpTab[o];
    k++;
  }
  for(int o = j; o <= e; o++){
    arr[k] = helpTab[o];
    k++;
  }
}

void sortArr(int b, int e){
  if(b<e){
    int mid = (b+e)/2;
    sortArr(b,mid);
    sortArr(mid+1,e);
    merge(b,mid,e);
  }
}

void obt(int beg, int end){
  int k = 0;
  for(int a = beg; a <= end; a++){
    int temp = GetElement(a);
    if(temp < 6){
      nums[temp]++;
      for(int b = temp+1; b <= 5; b++){
        smallerThan[b]++;
      }
    }
    arr[k] = (-1)*temp;
    k++;
  }
}

void master(){
  result += counter;
  for(int inst = 1; inst < NumberOfNodes(); inst++) {
      Receive(inst);
      result += GetLL(inst);
  }
  cout << result << endl;
}

void slave(){
  int start = (MyNodeId()*period);
  int end = min(size,start+period);
  end--;
  int currSize = end - start;
  obt(start,end);
  sortArr(0,currSize);
  for(int inst = MyNodeId()+1; inst < NumberOfNodes(); inst++){
    for(int a = 5; a >= 2; a--){
      Receive(inst);
      counter += (long long)(nums[a]*GetInt(inst));
    }
  }
  for(int inst = MyNodeId()-1; inst >= 0; inst--){
    for(int a = 5; a >= 2; a--){
      int packet = smallerThan[a];
      PutInt(inst,packet);
      Send(inst);
    }
  }
  if(MyNodeId()!=0){
    long long finalPacket = counter;
    PutLL(0,counter);
    Send(0);
  }
}

int main(){
  size = GetN();
  slave();
  if(MyNodeId() == 0){
    master();
  }
}