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

#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

struct Node {
  Node(int h = 0, long long s1 = 0, long long s2 = 0) : height(h), sumOfRectangles(s1), sumOfNums(s2) {}
  int height;
  long long sumOfRectangles;
  long long sumOfNums;
};

bool operator<(const Node &n1, const Node &n2) { return n1.height < n2.height; }

int main() {
  int myNodeId = MyNodeId();
  int numOfNodes = NumberOfNodes();

  int numOfRows = GetFieldHeight();
  int numOfCols = GetFieldWidth();

  vector<int> heights;
  heights.resize(numOfCols / numOfNodes + 1, 0);

  int step = numOfRows / numOfNodes;
  int whoToSend = 0, curr = step;

  if (step != 0) {
    for (int row = 0; row < numOfRows; ++row, ++curr) {
      if (curr ==  step) {
        PutChar(whoToSend, 'a');
        for (int i = 0, col = myNodeId; col < numOfCols; ++i, col += numOfNodes) {
          PutInt(whoToSend, heights[i]);
        }
        Send(whoToSend);
        curr = 0;
        ++whoToSend;
        if (whoToSend == numOfNodes) {
          break;
        }
      }
      for (int col = myNodeId, i = 0; col < numOfCols; col += numOfNodes, ++i) {
        if (IsUsableCell(row, col)) {
          ++heights[i];
        } else {
          heights[i] = 0;
        }
      }
    }
  }

  int startRow = numOfRows / numOfNodes * myNodeId;
  int endRow = startRow + numOfRows / numOfNodes;
  if (myNodeId == numOfNodes - 1) {
    endRow = numOfRows;
  }
  if (endRow == 0) {
    return 0;
  }
  vector<int> hs;
  hs.resize(numOfCols, 0);
  if (step != 0) {
    for (int i = 0; i < numOfNodes; ++i) {
      Receive(i);
      GetChar(i);
      for (int j = i; j < numOfCols; j += numOfNodes) {
        hs[j] = GetInt(i);
      }
    }
  }

  long long rectangles = 0;
  vector<Node> rects;
  rects.resize(numOfRows);
  for (int row = startRow; row < endRow; ++row) {
    int rectsMaxPos = 0;
    for (int currCol = numOfCols - 1; currCol >= 0; --currCol) {
      if (not IsUsableCell(row, currCol)) {
        hs[currCol] = 0;
        rectsMaxPos = 0;
        continue;
      }
      if (rectsMaxPos == 0) {
        rects[0].height = ++hs[currCol];
        rects[0].sumOfRectangles = rects[0].height;
        rects[0].sumOfNums = 1;
        rectsMaxPos = 1;
        rectangles += rects[0].sumOfRectangles;
        continue;
      }
      Node newNode;
      newNode.height = ++hs[currCol];
      int pos = distance(rects.begin(), lower_bound(rects.begin(), rects.begin() + rectsMaxPos, newNode));
      rects[pos].height = hs[currCol];
      if (pos == 0) {
        rects[0].sumOfNums = rects[rectsMaxPos - 1].sumOfNums + 1;
        rects[0].sumOfRectangles = rects[0].height * rects[0].sumOfNums;
        rectsMaxPos = 1;
        rectangles += rects[0].sumOfRectangles;
        continue;
      }
      rects[pos].sumOfNums = rects[rectsMaxPos - 1].sumOfNums + 1;
      rects[pos].sumOfRectangles = rects[pos].height * (rects[pos].sumOfNums - rects[pos - 1].sumOfNums) + rects[pos - 1].sumOfRectangles;
      rectsMaxPos = pos + 1;
      rectangles += rects[pos].sumOfRectangles;
    }
  }
  if (step == 0) {
    cout << rectangles << endl;
    return 0;
  }
  PutLL(numOfNodes - 1, rectangles);
  Send(numOfNodes - 1);
  if (myNodeId != numOfNodes - 1) {
    return 0;
  }
  long long finalRes = 0;
  for (int i = 0; i < numOfNodes; ++i) {
    int sender = Receive(-1);
    finalRes += GetLL(sender);
  }
  cout << finalRes << endl;
}