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

#include <cstdio>
#include <cstdlib>

#define ul unsigned long long
#define ll long long

int depth[77777];
int s1[77777];
int s2[77777];
ul bh, bw;

ul sum3(ul len, ul g) {
  return len*(len+1)/2*g;
}

ul solveSequential(int offH, int offW, int h, int w) {
  int zh = offH + h;
  int zw = offW + w;
  ul res = 0;
  for(int i=0;i<h;i++) {
    int ii = i + offH;
    for(int j=0;j<w;j++) {
      int jj = j + offW;
      if((ii < bh) && (jj < bw)) {
        if(IsUsableCell(ii,jj)) {
          depth[j]++;
        } else {
          depth[j]=0;
        }
      } else {
        depth[j] = 0;
      }
    }
    int us = 0;
    for(int j=0;j<=w;j++) {
      bool p = false;
      int k = 0;
      int g = 0;
      if(us > 0) {
        k = s1[us-1];
        g = s2[us-1];
      }

      int prevK = -1;
      ul len = 0;
      while(us > 0 && (g > depth[j])) {
        len = j-k;
        ul cur = sum3(len,g);
        res += cur;
        if(prevK != -1) {
          res -= sum3(j-prevK,g);
        }
        us--;
        prevK = k;
        p = true;
        if(us > 0) {
          k = s1[us-1];
          g = s2[us-1];
        }
      }
      if(p) {
        if(depth[j] > 0) {
          res -= sum3(len,depth[j]);
        }
      }
      if(((us==0) && (depth[j] > 0)) || (g < depth[j])) {
        s1[us] = p?prevK:j;
        s2[us] = depth[j];
        us++;
      }
    }
  }
  return res;
}

int main(int argc, char** argv) {
  bh = GetFieldHeight();
  bw = GetFieldWidth();
  int mi = (bh < bw) ? bh : bw;
  if(mi < 4000) {
    if(MyNodeId() == 0) {
      ul res = solveSequential(0,0,bh,bw);
      printf("%llu\n", res);
    }
  } else {
    int nodes = NumberOfNodes();
    int chunk = bw/nodes;
    if((bw%nodes)!=0) {
      chunk++;
    }
    int me = MyNodeId();
    int start = me * chunk;
    int end = (me+1)*chunk;
    ll res = (ll)solveSequential(0,start,bh,chunk);
    if(me != 0) {
      PutLL(0,res);
      Send(0);
    } else {
      for(int i=1;i<nodes;i++) {
        Receive(i);
        res += GetLL(i);
      }
      printf("%lld\n", res);
    }
  }
}