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"
#include <iostream>
#include <vector>
#include <stack>
#include <cassert>
using namespace std;

using LL = long long;
using STACK = vector<pair<int, int>>;

inline void add(LL& s, LL h, LL w)
{
  s += (w * (w + 1) / 2) * h;
}

STACK st;
int sts;

inline void reduce_stack(LL& sum, int pos)
{
  assert(sts > 0);
  auto tp = st[--sts];
  if (sts > 0) {
    add(sum, tp.first - st[sts-1].first, pos - tp.second);
  } else {
    add(sum, tp.first, pos);
  }
}

int main() {
  int n = GetFieldHeight(), m = GetFieldWidth();
  if (n <= MyNodeId()) {
    return 0;
  }
  int nodes_num = min(n, NumberOfNodes());
  int std_chunk_size = n / nodes_num;
  int my_chunk_size;
  if (MyNodeId() == nodes_num - 1) {
    my_chunk_size = n - (nodes_num - 1) * std_chunk_size;
  } else {
    my_chunk_size = std_chunk_size;
  }
  vector<int> t(m, 0);
  int beg = std_chunk_size * MyNodeId();
  for (int i = beg; i < beg + my_chunk_size; ++i) {
    for (int j = 0; j < m; ++j) {
      if (IsUsableCell(i, j)) {
        t[j] += 1;
      } else {
        t[j] = 0;
      }
    }
  }
  vector<int> s(m);
  if (MyNodeId() > 0)
  {
    int pred = MyNodeId() - 1;
    Receive(pred);
    for (int j = 0; j < m; ++j) {
      s[j] = GetInt(pred);
      if (t[j] == my_chunk_size) {
        t[j] += s[j];
      }
    }
  }
  if (MyNodeId() < nodes_num - 1)
  {
    int succ = MyNodeId() + 1;
    for (int j = 0; j < m; ++j) {
      PutInt(succ, t[j]);
    }
    Send(succ);
  }

  LL sum = 0;
  st.resize(m + 1);
  for (int i = beg; i < beg + my_chunk_size; ++i) {
    for (int j = 0; j < m; ++j) {
      if (IsUsableCell(i, j)) {
        s[j] += 1;
      } else {
        s[j] = 0;
      }
    }

    sts = 1;
    st[0] = make_pair(0, -1);
    for (int j = 0; j < m; ++j) {
      int last = j;
      while (sts > 0 && st[sts-1].first >= s[j]) {
        auto tp = st[--sts];
        if (sts > 0) {
          add(sum, min(tp.first - st[sts-1].first, tp.first - s[j]), j - tp.second);
        } else {
          add(sum, tp.first, j);
        }
        last = tp.second;
      }
      st[sts++] = make_pair(s[j], last);
    }

    while (sts > 0) {
      reduce_stack(sum, m);
    }
  }

  if (MyNodeId() > 0)
  {
    PutLL(0, sum);
    Send(0);
    return 0;
  }

  LL sumall = sum;
  for (int i = 1; i < nodes_num; ++i) {
    int node = Receive(-1);
    sumall += GetLL(node);
  }
  cout << sumall << endl;

  return 0;
}