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

#include <cstdio>
#include <algorithm>

typedef unsigned long long ullong;

const int MAX_W = 75009;
int row[MAX_W];
int end_row[MAX_W];

const int MAX_CHUNK_SIZE = 40000;

std::pair<int, int> srowp[MAX_W];
int nl[MAX_W];
ullong res[MAX_W];

void send_array(int to, int size, const int* array) {
  int sent = 0;
  while (sent < size) {
    int chunk = std::min(size-sent, (int)(MAX_CHUNK_SIZE/sizeof(int)));
    for (int i = 0; i < chunk; ++i) {
      PutInt(to, array[sent+i]);
    }
    Send(to);
    sent += chunk;
  }
}

void recv_array(int from, int size, int* array) {
  int recvd = 0;
  while (recvd < size) {
    int chunk = std::min(size-recvd, (int)(MAX_CHUNK_SIZE/sizeof(int)));
    Receive(from);
    for (int i = 0; i < chunk; ++i) {
      array[recvd+i] = GetInt(from);
    }
    recvd += chunk;
  }
}

int main() {
  int w = GetFieldWidth();
  int h = GetFieldHeight();
  int start = 0;
  int end = h;
  if (h < 100) {
    if (MyNodeId() != 0) {
      return 0;
    }
  } else {
    start = (MyNodeId()*h)/NumberOfNodes();
    end = ((MyNodeId()+1)*h)/NumberOfNodes();
    for (int i = start; i < end; ++i) {
      for (int j = 0; j < w; ++j) {
        if (IsUsableCell(i, j)) {
          ++end_row[j];
        } else {
          end_row[j] = 0;
        }
      }
    }
    if (MyNodeId() != 0) {
      recv_array(MyNodeId()-1, w, row);
      for (int j = 0; j < w; ++j) {
        if (end_row[j] == end-start) {
          end_row[j] += row[j];
        }
      }
    }
    if (MyNodeId() != NumberOfNodes()-1) {
      send_array(MyNodeId()+1, w, end_row);
    }
  }
  ullong sum = 0;
  for (int i = start; i < end; ++i) {
    int z = 0;
    srowp[0].first = 0;
    srowp[0].second = -1;
    for (int j = 0; j < w; ++j) {
      if (IsUsableCell(i, j)) {
        ++row[j];
      } else {
        row[j] = 0;
      }
      while (srowp[z].first > row[j]) {
        nl[srowp[z].second] = j;
        res[srowp[z].second] = ((ullong)j-srowp[z].second)*srowp[z].first;
        --z;
      }
      if (row[j] != 0) {
        srowp[++z] = {row[j], j};
      } else {
        nl[j] = -1;
        res[j] = 0;
      }
    }
    while (srowp[z].first > 0) {
      nl[srowp[z].second] = -1;
      res[srowp[z].second] = ((ullong)w-srowp[z].second)*srowp[z].first;
      --z;
    }
    for (int j = w-1; j >= 0; --j) {
      if (nl[j] != -1) {
        res[j] += res[nl[j]];
      }
      sum += res[j];
    }
  }
  if (MyNodeId() == 0) {
    if (h >= 100) {
      for (int j = 1; j < NumberOfNodes(); ++j) {
        Receive(j);
        long long recvd = GetLL(j);
        sum += (ullong)recvd;
      }
    }
    printf("%llu\n", sum);
  } else {
    PutLL(0, (long long)sum);
    Send(0);
  }
}