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
#include "dzialka.h"
#include "message.h"
using namespace std;
#include <iostream>
#include <stack>
#include <cstring>

int ID;
int rows;
int cols;
int myRowsBeg, myRowsEnd;
int nodes;
const int MAX = 75005;
typedef unsigned long long LL;
int* Gprev;
int* Gcurr;
//obliczam do Gprev
void FillArray()
{
    for(int i = myRowsBeg; i < myRowsEnd; ++i)
    {
        for(int j = 0; j < cols; ++j)
            Gcurr[j] = IsUsableCell(i, j) ? Gprev[j]+1 : 0;
        swap(Gcurr, Gprev);
    }
}
//odbieram do Gcurr
void ReceiveArray()
{
    for(int i = 0; i < cols; i += 8192)
    {
        Receive(ID-1);
        for(int j = 0; j < 8192 && i+j < cols; ++j)
            Gcurr[i+j] = GetInt(ID-1);
    }
}
//Gprev to tab obliczona
//Gcurr to tab odebrana
void SendArray()
{
    int myRowsCt = myRowsEnd-myRowsBeg;
    for(int i = 0; i < cols; i += 8192)
    {
        for(int j = 0; j < 8192 && i+j < cols; ++j)
            PutInt(ID+1, Gprev[i+j] == myRowsCt ? Gcurr[i+j]+myRowsCt : Gprev[i+j]);
        Send(ID+1);
    }
}

LL getRects(LL width, LL height)
{
    return ((width*(width+1))/2)*height;
}
//Gcurr to odebrana/obliczona
//Gprev to na nowo obliczona
LL ComputeRow(int row)
{
    int myRowsCt = myRowsEnd-myRowsBeg;
    LL rectCount = 0;
    for(int i = 0; i < cols; ++i)
        Gprev[i] = IsUsableCell(row, i) ? Gcurr[i]+1 : 0;
    stack<pair<int, int>> s;
    s.push(make_pair(0, -1));
    for(int j = 0; j <= cols; ++j)
    {
        pair<int, int> p = s.top();
        int odl = j;
        while(p.first > Gprev[j])
        {
            s.pop();
            int minHeight = max(Gprev[j], s.top().first);
            rectCount += getRects(j-p.second, p.first-minHeight);
            odl = p.second;
            p = s.top();
        }
        if(p.first < Gprev[j])
            s.push(make_pair(Gprev[j], odl));
    }
    swap(Gcurr, Gprev);
    return rectCount;
}

void GetResults()
{
    LL sum = 0;
    for(int i = 0; i < nodes; ++i)
    {
        int rec = Receive(-1);
        sum += GetLL(rec);
    }
    cout << sum << endl;
}

int main() {
  Gprev = new int[MAX];
  Gcurr = new int[MAX];
  memset(Gprev, 0, MAX*sizeof(int));
  memset(Gcurr, 0, MAX*sizeof(int));
  ID = MyNodeId();
  rows = GetFieldHeight();
  cols = GetFieldWidth();
  nodes = NumberOfNodes();
  myRowsBeg = ID*(rows/nodes);
  myRowsEnd = myRowsBeg+rows/nodes;
  if(ID == nodes-1) myRowsEnd += rows%nodes;

  FillArray();
  if(ID > 0)
    ReceiveArray();
  if(ID == 0)
    memset(Gcurr, 0, MAX*sizeof(int));
  if(ID < nodes-1)
    SendArray();
  LL sum = 0;
  for(int i = myRowsBeg; i < myRowsEnd; ++i)
    sum += ComputeRow(i);
  PutLL(0, sum);
  Send(0);
  if(ID == 0)
    GetResults();
  delete [] Gprev;
  delete [] Gcurr;
}