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
// Michał Seweryn

#include "dzialka.h"

#include "message.h"

#include "bits/stdc++.h"
using namespace std;

int R (int i) {
    return (int) ((long long) i * GetFieldHeight() / NumberOfNodes());
}

int C (int i) {
    return (int) ((long long) i * GetFieldWidth() / NumberOfNodes());
}


int main() {
  vector<int> b(GetFieldWidth(), 0);
  long long num_rect = 0;
  {
    int c0 = C(MyNodeId());
    int c1 = C(MyNodeId() + 1);
    vector<int> a(c1-c0, 0);
    for (int i = 0; i + 1 < NumberOfNodes(); ++i) {
      //if(MyNodeId() == 0) cerr << "0 ieration " << i << '\n';
      int r0 = R(i);
      int r1 = R(i + 1);
      for (int r = r0; r < r1; ++r) {
        for (int c = c0; c < c1; ++c) {
          if (IsUsableCell(r, c)) {
            ++a[c-c0];
          } else {
            a[c-c0] = 0;
          }
        }
      }
      //cerr << "a[..] = ";
      //for (int x : a) {cerr << x << ' ';}
      //cerr << '\n';

      if (i + 1 == MyNodeId()) {
        copy(a.begin(), a.end(), b.begin() + c0);
      } else {
        for (int c = c0; c < c1; ++c) {
          PutInt(i + 1, a[c-c0]);
        }
        //cerr << MyNodeId() << " sends to " << i + 1 << " a\n";
        Send(i + 1);
      }
    }
  }
  {
    if (MyNodeId() != 0) {
      for (int j = 0; j < NumberOfNodes(); ++j) {
        if (j != MyNodeId()) {
          //cerr << MyNodeId() << " receives from " << j << " b\n";
          Receive(j);
          int c0 = C(j);
          int c1 = C(j + 1);
          for (int c = c0; c < c1; ++c) {
            b[c] = GetInt(j);
          }
        }
      }
    }
    int r0 = R(MyNodeId());
    int r1 = R(MyNodeId()+1);
    b.push_back(0);
    //for (auto x : b) {cerr << x << ' ';} cerr << '\n';
    for (int r = r0; r < r1; ++r) {
      vector<pair<int, int>> s;
      for (int c = 0; c < (int) b.size(); ++c) {
        b[c] = (c < (int) b.size() - 1 && IsUsableCell(r, c)) ? b[c] + 1 : 0;
        //cerr << b[c] << ' ';
        int r0, c0 = c;
        while (!s.empty() && s.back().first >= b[c]) {
          tie(r0, c0) = s.back(); s.pop_back();
          int r1 = max(s.empty() ? 0 : s.back().first, b[c]);
          num_rect += (long long) (r0 - r1) * (c - c0 + 1) * (c - c0) / 2;
        }
        s.emplace_back(b[c], c0);
      }
      //cerr << '\n';
    }
  }
  if (MyNodeId() != 0) {
    PutLL(0, num_rect);
    //cerr << MyNodeId() << " sends to " << 0 << " c\n";
    Send(0);
  } else {
    for (int i = 1; i < NumberOfNodes(); ++i) {
      //cerr << MyNodeId() << " receives from " << i  << " d\n";
      Receive(i);
      num_rect += GetLL(i);
    }
    cout << num_rect << '\n';
  }
}