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 <cstdio>
#include <algorithm>
#include <stack>

#include "dzialka.h"
#include "message.h"

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define LL long long
#define PII pair<int, int>
#define MP make_pair
#define FI first
#define SE second
  
using namespace std;

const int maxlen = 75010;
const int maxnodelen = 760;
const int messageLimit = 990;

int numNodes;
int nodeId;

LL row[maxlen];

char use[maxnodelen][maxlen];
int top[maxlen];
int down[maxlen];

stack<PII> st;

void receiveTop(int from, int to) {
  if (nodeId == 0) {
    return;
  }
  Receive(nodeId - 1);
  FOR(c, from, to - 1) {
    top[c] = GetLL(nodeId - 1);
  }
}

void sendDown(int from, int to) {
  if (nodeId == numNodes - 1) {
    return;
  }
  FOR(c, from, to - 1) {
    PutLL(nodeId + 1, down[c]);
  }
  Send(nodeId + 1);
}

int main() {
  numNodes = NumberOfNodes();
  nodeId = MyNodeId();

  int maxC = GetFieldWidth();
  int maxR = GetFieldHeight();
  
  int nodeRRange = maxR/numNodes + 1;
  int fromR = nodeId*nodeRRange;
  int toR = min((nodeId + 1)*nodeRRange, maxR);

  int colBatch = maxC/messageLimit + 1;
  
  int toC;
  for(int fromC = 0; fromC <= maxC - 1; fromC += colBatch) {
    toC = min(fromC + colBatch, maxC);
    receiveTop(fromC, toC);
    FOR(c, fromC, toC - 1) {
      down[c] = top[c];
    }
    FOR(r, fromR, toR - 1) {
      FOR(c, fromC, toC - 1) {
        use[r - fromR][c] = IsUsableCell(r, c);
        if (!use[r - fromR][c]) {
          down[c] = r + 1;
        }
      }
    }
    sendDown(fromC, toC);
  }
  
  int height;
  int rectFromC;
  LL res = 0;
  FOR(r, fromR, toR - 1) {
    while (!st.empty()) {
      st.pop();
    }
    FOR(c, 0, maxC - 1) {
      if (!use[r - fromR][c]) {
        top[c] = r + 1;
      }
      height = r - top[c] + 1;
      rectFromC = c;
      while (!st.empty() && st.top().SE > height) {
        rectFromC = st.top().FI;
        st.pop();
      }
      if (!st.empty() && st.top().SE == height) {
        rectFromC = st.top().FI;
      }
      row[c] = ((rectFromC == 0) ? 0 : row[rectFromC - 1]) + (LL)height*(LL)(c - rectFromC + 1);
      res += row[c];
      if (height > 0 && (st.empty() || st.top().SE < height)) {
        st.push(MP(rectFromC, height));
      }
    }
  }
  
  if (nodeId == 0) {
    FOR(source, 1, numNodes - 1) {
      Receive(source);
      res += GetLL(source);
    }
    printf("%lld\n", res);
  } else {
    PutLL(0, res);
    Send(0);
  }
  return 0;
}