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

#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <sstream>
#include <stack>
#include <vector>
using namespace std;

long long processRow(vector<long> G, long y, int n) {
  long long counter = 0;
  // for (int i = 0; i<=n+1; i++) {
  //   cout << G[i] << " ";
  // }
  // cout <<"\n";
  stack<pair<long, long> > s;
  long last_start = -1;
  long last_end = -1;
  for (int i = 1; i <= n+1; ++i) {
    bool was_pop = false;
    pair<long, long> kg;
    pair<long, long> kpgp;
    long k,kp,g,gp;
    if (!s.empty()) {
      kg = s.top();
     // cout << "kg taken " << endl << flush;
      k = kg.first;
      g = kg.second;
    }
    while ((!s.empty()) && (g > G[i])) {
     // cout << "here while" << endl << flush;
    //  cout << "group: " << k << "," << i - 1 << "x" << (y - G[i-1] + 1) << "," << y << endl;
    //  cout << "* g="<< g << "; G[i-1]=" << G[i-1] << "; G[i]="<< G[i] << endl;
      //cout << "area=" << i-k << "x" << G[i-1] << "=" << (i-k)*G[i-1] << endl;
      long long xL = i-k;
      long long group_count = 0;
      long prev_g = g;
    //  cout << "xL=" << xL << ",yL=" << yL << endl;
      
      //cout << "last_start=" << last_start << ",last_end=" << last_end << endl;
      // if (last_start >= k) {
      //   long lL = last_end - last_start + 1;
      //   counter -= (lL*(lL+1) / 2) * yL;
      // }
      // last_start = k;
      // last_end = i - 1;
      kpgp = s.top();
    //  cout << "after s.top()" << endl << flush;
    //  cout << "is empty2=" << s.empty() << endl << flush;
      s.pop();
    //  cout << "after s.pop()" << endl << flush;
    //  cout << "is empty3=" << s.empty() << endl << flush;

      kp = kpgp.first;
      gp = kpgp.second;
    //  cout << "kp=" << kp << ", gp =" << gp << endl << flush;
      was_pop = true;
      if (!s.empty()) {
        kg = s.top();
        k = kg.first;
        g = kg.second;
        // cout << "seeing next: " << g << endl;
        // group_count = (xL*(xL+1) / 2) * (yL - g);
        // cout << "G[i-1]=" << G[i-1] << "g="<< G[i] << endl;
      } else {
        g = 0;
      }
      //cout << "prev g = " << prev_g << " final g = " << g << endl;
      group_count = (xL*(xL+1) / 2) * (prev_g - max(G[i], g));
      //cout << "group_count = " << group_count << endl;
      counter += group_count;
    }
    if ((s.empty() && G[i] > 0) || (g < G[i])) {
      pair<long, long> newpair;
      if (was_pop) {
        newpair = make_pair(kp, G[i]);
      } else{
        newpair = make_pair(i, G[i]);
      }
      s.push(newpair);
    }
  }  //   cout << i;
  return counter;
}

int main() {
  if (MyNodeId() > 0) {
    return 0;
  }

  const int n = GetFieldHeight();
  const int m = GetFieldWidth();

  //cout << "n=" << n << " m="<< m << endl;
  vector<long> G(m + 2);
  long long total = 0;
  for (int j = 1; j <= n; j++) {
    for(int i = 1; i <= m; i++) {
      if (IsUsableCell(j-1, i-1)) {
        G[i] = G[i] + 1;
      } else {
        G[i] = 0;
      }
    }
    long long counter = processRow(G, j, m);
   // cout << "--- row count: " << counter << endl;
    total += counter;
  }
  cout << total << "\n";
  return 0;
}