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
#include "dzialka.h"
#include "message.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX = 75005;
int h[MAX], p[MAX], sz[MAX], vis[MAX];
int N, ID, n, m;

/* ----------------------------------- CZESC 1 ----- */

void fun1()
{
  int k = m / N + 1;
  int k2 = n / N + 1;
  int pocz = ID * k, konc = (ID + 1) * k - 1;
  konc = min(konc, m-1);
  if (pocz >= m) return;

  for (int i = 0; i < n; i++)
  {
    for (int j = pocz; j <= konc; j++)
    {
      h[j]++;
      if (!IsUsableCell(i, j)) 
        h[j] = 0;
    }
    if (i % k2 == 0)
    {
      int ID2 = i / k2;
      for (int j = pocz; j <= konc; j++)
        PutInt(ID2, h[j]);
      Send(ID2);
    }
  }
}

/* ----------------------------------- CZESC 2 ----- */

int Find(int x)
{
  if (p[x] == x) return x;
  return p[x] = Find(p[x]);
}
void Union(int a, int b)
{
  a = Find(a); b = Find(b);
  if (a != b) sz[a] += sz[b];
  p[b] = a;
}

unsigned long long fun2()
{
  int k = n / N + 1;
  int k2 = m / N + 1;
  int pocz = ID * k, konc = (ID + 1) * k - 1;
  konc = min(konc, n-1);
  if (pocz >= n) return 0;

  for (int j = 0; j < m; j++) if (j % k2 == 0)
  {
    int ID2 = j / k2;
    Receive(ID2);
    for (int j2 = j; j2 < min(j + k2, m); j2++)
      h[j2] = GetInt(ID2);
  }

  unsigned long long result = 0;
  for (int i = pocz; i <= konc; i++)
  {
    if (i != pocz)
    {
      for (int j = 0; j < m; j++)
      {
        h[j]++;
        if (!IsUsableCell(i, j))
          h[j] = 0;
      }
    }
    
    vector<pair<int,int>> pos;
    p[0] = 0; sz[0] = 0; p[m+1] = m+1; sz[m+1] = 0;
    for (int j = 0; j < m; j++)
    {   
      p[j+1] = j+1; sz[j+1] = 1; vis[j+1] = 0;
      pos.push_back({h[j], j+1});
    }
    sort(pos.begin(), pos.end());
    reverse(pos.begin(), pos.end());
    for (auto pp: pos)
    {
      vis[pp.second] = 1;
      int sz1 = 0; if (vis[pp.second-1]) sz1 = sz[Find(pp.second-1)];
      int sz2 = 0; if (vis[pp.second+1]) sz2 = sz[Find(pp.second+1)];
      result += 1LL * (sz1+1) * (sz2+1) * pp.first;
      if (vis[pp.second-1]) Union(pp.second, pp.second-1);
      if (vis[pp.second+1]) Union(pp.second, pp.second+1);
    }
  }
  return result;
}

int main() 
{
  N = NumberOfNodes();
  ID = MyNodeId();
  n = GetFieldHeight();
  m = GetFieldWidth();

  fun1();
  
  long long result = fun2();
  if (ID != 0)
  {
    PutLL(0, result);
    Send(0);
  }
  else
  {
    unsigned long long elo = result;
    for (int i = 1; i < N; i++)
    {
      Receive(i);
      elo += GetLL(i);
    }
    std::cout << elo << "\n";
  }
}