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
127
128
129
130
131
132
133
134
// 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 <bits/stdc++.h>
using namespace std;

bitset<75009> tab[751];
int init_sumy[75009];
int sumy[75009];
pair<int, int> heap[75009];

int main() {
  /*
  if (MyNodeId() > 0)
    return 0;

  const int NumRows = GetFieldHeight();
  const int NumCols = GetFieldWidth();

  long long Result = 0;
  for (int Row = 0; Row < NumRows; ++Row)
    for (int Col = 0; Col < NumCols; ++Col)
      if (IsUsableCell(Row, Col))
        ++Result;

  std::cout << Result << "\n";
  */
  int id = MyNodeId();
  int nodes = NumberOfNodes();

  int height = GetFieldHeight();
  int width = GetFieldWidth();

  int it = 0;

  for(int i=0;i<750;i++)
  {
    for(int j=0;j<75000;j++)
    {
      if(i+750*id < height && j < width)
        tab[i][j] = IsUsableCell(i+750*id, j);
    }
  }

  for(int i=0;i<750;i++)
  {
    if(id != 0)
    {
      Receive(id-1);
      for(int j=0;j<100;j++)
      {
        int tmp = GetInt(id-1);
        if(100*i + j >= width)
          continue;
        if(tab[0][100*i + j])
          init_sumy[100*i + j] = tmp + 1;
        else
          init_sumy[100*i + j] = 0;
        sumy[100*i + j] = init_sumy[100*i + j];
      }
    }
    else
    {
      for(int j=0;j<100;j++)
        init_sumy[100*i + j] = tab[0][100*i + j];
      for(int j=0;j<100;j++)
        sumy[100*i + j] = init_sumy[100*i + j];
    }
    for(int k=1;k<750;k++)
    {
      for(int j=0;j<100;j++)
      {
        if(tab[k][100*i + j])
          sumy[100*i + j] = sumy[100*i + j] + 1;
        else
          sumy[100*i + j] = 0;
      }
    }
    if(id < nodes - 1)
    {
      for(int j=0;j<100;j++)
      {
        PutInt(id + 1, sumy[100*i + j]);
      }
      Send(id + 1);
    }
  }
  long long suma = 0;
  for(int i=0;i<750;i++)
  {
    it = 0;
    heap[it] = make_pair(-1,0);
    for(int j=0;j<75001;j++)
    {
      if(i==0)
        sumy[j] = init_sumy[j];
      else if(tab[i][j])
        sumy[j]++;
      else
        sumy[j]=0;
      //if(j<10 && i<10)
      //  cerr<<"sumy["<<i<<"]["<<j<<"] = "<<sumy[i][j]<<endl;
      long long prev = 0;
      while(heap[it].second > sumy[j])
      {
        long long top = heap[it].second - sumy[j];
        long long left = j - heap[it-1].first - 1;
        it--;
        suma += (top*left*(left+(long long)1))/(long long)2;
        suma -= (top*prev*(prev+(long long)1))/(long long)2;
        prev = left;
      }
      heap[++it] = make_pair(j, sumy[j]);
    }
  }
  if(id != 0)
  {
    PutLL(0, suma);
    Send(0);
  }
  else
  {
    for(int i=1;i<nodes;i++)
    {
      Receive(i);
      suma += GetLL(i);
    }
    cout<<suma<<endl;
  }
  return 0;
}