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
125
126
// Błędne rozwiązanie do zadania Działka 2.
// Na pojedynczym węźle wypisuje liczbę dostępnych kwadracików.

#include "dzialka.h"
#include "message.h"

#include <iostream>
#include <vector>
using namespace std;

using ull = unsigned long long;

using para = pair<long long, ull>;

int nodeNo;
int nodeCount;

long long Hei;
long long Wid;

long long A;
long long B;

const long long FRAGMENT = 100;
const long long MAXWID = 75000;

ull depth[MAXWID];

void calculatePredepths() {
  if (nodeNo == 0) {
    for (int i = 0; i < Wid; i++) {
      depth[i] = 0;
    }
  }

  for (int i = 0; i < Wid; i++) {
    if (nodeNo > 0) {
      if (i % FRAGMENT == 0) {
        Receive(nodeNo - 1);
      }
      depth[i] = GetLL(nodeNo - 1);
    } else {
      depth[i] = 0;
    }

    if (nodeNo + 1 < nodeCount) {
      ull d = depth[i];
      for (int j = A; j < B; j++) {
        if (IsUsableCell(j, i)) {
          d++;
        } else {
          d = 0;
        }
      }
      PutLL(nodeNo + 1, d);

      if (i % FRAGMENT == FRAGMENT - 1 || i + 1 == Wid) {
        Send(nodeNo + 1);
      }
    }
  }
}


ull calculateRow(int row) {
  ull result = 0;
  vector<para> S;
  S.push_back(para(-1, 0));
  ull area = 0;
  for (int i = 0; i < Wid; i++) {
    if (IsUsableCell(row, i)) {
      depth[i]++;
    } else {
      depth[i] = 0;
    }
    ull d = depth[i];
    while (S.back().second > d) {
      para p = S.back();
      S.pop_back();
      if (S.back().second >= d) {
        // nadal będziemy usuwać elementy
        area -= (p.second - S.back().second) * (i - p.first);
      } else {
        // tylko przycinamy element;
        area -= (p.second - d) * (i - p.first);
        S.push_back(para(p.first, d));
      }
    }

    if (S.back().second < d) {
      S.push_back(para(i, d));
    }
    area += d;
    result += area;
  }
  return result;
}


int main() {
  Hei = GetFieldHeight();
  Wid = GetFieldWidth();
  nodeCount = NumberOfNodes();
  nodeNo = MyNodeId();

  A = (Hei + nodeCount - 1) / nodeCount * nodeNo;
  B = (Hei + nodeCount - 1) / nodeCount * (nodeNo + 1);
  if (B > Hei) B = Hei;

  calculatePredepths();
  ull result = 0;
  for (int i = A; i < B; i++) {
    result += calculateRow(i);
  }

  if (nodeNo > 0) {
    PutLL(0, result);
    Send(0);
  } else {
    for (int i = 1; i < nodeCount; i++) {
      Receive(i);
      result += GetLL(i);
    }
    cout << result << endl;
  }
}