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
#include "teatr.h"
#include <iostream>
#include "message.h"


using namespace std;


struct rNode
{
  int data;
  int eStart;
  int eMed;
  int eFinish;
  long long eValue;
  struct rNode *up;
  struct rNode *left;
  struct rNode *right;
};

rNode *Dat[100000];
rNode *Root;

struct rNode* newNode(rNode *aUp, int aStart, int aFinish)
{
  // Allocate memory for new node
  struct rNode* oNode = new rNode;

  // Assign data to this node
  //oNode->data = data;
  oNode->up     = aUp;
  oNode->eStart = aStart;
  oNode->eMed   =(aStart+aFinish)/2;
  oNode->eFinish= aFinish;
  oNode->eValue = 0;

  // Initialize left and right children as NULL
  oNode->left = nullptr;
  oNode->right = nullptr;
  return oNode;
}

void PrintNode(rNode *aNode){
    cout<<"Value="<<aNode->eValue<<" Start="<<aNode->eStart<<" Finish="<<aNode->eFinish<<" Med="<<aNode->eMed<<" Left="<<bool(aNode->left!=nullptr)<<" Rigth="<<bool(aNode->right!=nullptr)<<endl;
}

rNode* TreeCreate( rNode *aUp, int aStart, int aFinish){
    rNode * oNode = newNode( aUp, aStart,aFinish);
    if(aStart<aFinish){
        int oMed = (aStart+aFinish)/2;
        oNode->left = TreeCreate( oNode, aStart, oMed);
        oNode->right = TreeCreate( oNode, oMed+1, aFinish);
    }else{
        Dat[aStart] = oNode;
    }
    return oNode;
}

long long TestTall(int aHeigth){
    rNode *oNode = Root;
    long long oSum = 0;
    while(oNode!=nullptr){
//        PrintNode(oNode);
        if(aHeigth<=oNode->eMed){
            rNode *oTemp = oNode->right;
            if(oTemp!=nullptr){oSum+=oTemp->eValue;};
            oNode = oNode->left;
        }else{
            oNode = oNode->right;
        }
    }
    return oSum;
}

void SidTall(int aHeigth){
    rNode* oNode = Dat[aHeigth];
    while (oNode!=nullptr){
        oNode->eValue++;
        oNode = oNode->up;
    }
}

void PrintDat(int aStart, int aFinish){
    for(int oLoop=aStart;oLoop<aFinish;oLoop++){
        cout<<"Numer="<<oLoop<< "Value="<<Dat[oLoop]->eValue<<" Left="<<bool(Dat[oLoop]->left!=nullptr)<<" Rigth="<<bool(Dat[oLoop]->left!=nullptr)<<endl;
    }
}

void ReadData(){
    int oNodeCount = NumberOfNodes();
    int MyNode = MyNodeId();
    int ItemCount = GetN();
    int lowTriger = MyNode * 10000 +1;
    int highTriger = (MyNode + 1 ) * 10000;
    long long highCount = 0;
    long long oSum = 0;
    for(int oLoop=0;oLoop<ItemCount;oLoop++){
        int oItem = GetElement(oLoop);
        if(oItem>=lowTriger){
            if(oItem<=highTriger){
                oSum += TestTall(oItem) + highCount;
                SidTall(oItem);
            }else{
                highCount++;
            }
        }
    }
    PutLL(0,oSum);
    Send(0);
}

int main()
{
    Root = TreeCreate(nullptr,0,10001);
    ReadData();
    int oNodeCount = NumberOfNodes();
    int MyNode = MyNodeId();
    long long oSum = 0;
    if(MyNode==0){
        for(int oLoop=0;oLoop<oNodeCount;oLoop++){
            Receive(oLoop);
            oSum += GetLL(oLoop);
        }
        cout << oSum << endl;
    }
    return 0;
}