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

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

class RowComputer {
 public:
  RowComputer() : sum_x_delta_y_(0) {
    Push(-1, 0);
  }

  void Add(int x, const int y) {
    while (y < s_.top().second) {
      x = s_.top().first;
      Pop();
    }
    if (y == s_.top().second) return;
    Push(x, y);
  }

  long long Get(const int xx) const {
    // For each (x, y) in stack, add (xx - x + 1) * (y - y_prev).
    // 1. Add (xx + 1) * top_y.
    // 2. Subtract sum_x_delta_y.
    return static_cast<long long>(xx + 1) * s_.top().second - sum_x_delta_y_;
  }

 private:
  void Pop() {
    const int x = s_.top().first;
    const int y = s_.top().second;
    s_.pop();
    // cerr << "-" << x << ' ' << y << endl;
    sum_x_delta_y_ -= static_cast<long long>(x) * (y - s_.top().second);
    // cerr << "x_delta_y:" << sum_x_delta_y_ << endl;
  }

  void Push(const int x, const int y) {
    // cerr << "+ " << x << ' ' << y << endl;
    if (!s_.empty()) sum_x_delta_y_ += static_cast<long long>(x) * (y - s_.top().second);
    s_.push(make_pair(x, y));
    // cerr << "x_delta_y:" << sum_x_delta_y_ << endl;
  }

  long long sum_x_delta_y_;
  stack<pair<int, int> > s_;
};

void Split(const int n, const int k, vector<int>* v) {
  v->resize(k + 1);
  for (int i = 0; i <= k; ++i) (*v)[i] = (n * i) / k;
}

int main() {
  const int num_rows = GetFieldHeight();
  const int num_cols = GetFieldWidth();

  vector<int> x, y;
  Split(num_rows, NumberOfNodes(), &y);
  Split(num_cols, NumberOfNodes(), &x);

  const int t = y[MyNodeId()    ];
  const int b = y[MyNodeId() + 1];

  vector<int> top(num_cols);
  for (int i = 1; i < x.size(); ++i) {
    const int l = x[i - 1];
    const int r = x[i    ];
    if (MyNodeId() > 0) {
      Receive(MyNodeId() - 1);
      for (int j = l; j < r; ++j) top[j] = GetInt(MyNodeId() - 1);
    }
    if (MyNodeId() < NumberOfNodes() - 1) {
      for (int j = l; j < r; ++j) {
        int curr = top[j];
        for (int k = t; k < b; ++k) if (IsUsableCell(k, j)) ++curr; else curr = 0;
        PutInt(MyNodeId() + 1, curr);
      }
      Send(MyNodeId() + 1);
    }
  }

  long long result = 0;
  for (int i = t; i < b; ++i) {
    for (int j = 0; j < num_cols; ++j) if (IsUsableCell(i, j)) ++top[j]; else top[j] = 0;
    RowComputer c;
    for (int j = 0; j < num_cols; ++j) {
      // cerr << j << ' ' << top[j] << endl;
      c.Add(j, top[j]);
      result += c.Get(j);
      // cerr << result << endl;
    }
  }

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

  if (MyNodeId() == 0) {
    for (int i = 1; i < NumberOfNodes(); ++i) {
      Receive(i);
      result += GetLL(i);
    }
    std::cout << result << "\n";
  }

  return 0;
}