#include <bits/stdc++.h>
#include "dzialka.h"
#include "message.h"

using namespace std;

#define REP(i, x) for( int i = 0; i < x; i++ )
#define FOR(i, x) for( int i = 1; i <=x; i++ )
#define BACK(i, x) for( int i = x; i >=1; i-- )
#define BACK_REP(i, x) for( int i = x-1; i >=0; i-- )
#define MP make_pair
#define ST first
#define ND second
#define LL long long

typedef pair<int, int> PI;

const int MAX_WIDTH = 75010;
int NODES;

int h;
int w;
int myself = MyNodeId();

int premie[MAX_WIDTH];
int specjalne_premie[MAX_WIDTH];
bool zastap[MAX_WIDTH];

int przedzial;
int moja_gora;
int moj_dol;

void znajdz_zakres(){ //liczy procesowi, które wiersze tablicy będzie przerabiał
    przedzial = (h / NODES) + 1;
    moja_gora = myself * przedzial;
    moj_dol = min((myself + 1) * przedzial, h);
}

/*  Każdemu procesowi liczy, jaka jest wysokość "słupa" dobrych elementów ponad jego przedziałem,
    wartość ta będzie trzymana w tablicy premie[].
    specjalne_premie[] trzymają wysokość takiego słupa dla segmentu przetwarzanego przez dany proces
    (kandydat do przekazania następnemu procesowi dla jego segmentu), którą być może trzeba poprawić
    wynikiem zwróconym z segmentu przetwarzającego wyższy fragment (poprawia druga pętla, wysyła - trzecia).
    zastap sprawdza, czy gdzieś na danym segmencie mamy zły element, co oznaczałoby, że nie możemy zwiększyć
    wyniku o to, co dostaliśmy z wyższej części tablicy (można by było zamiast sprawdzania zastap[k] sprawdzać,
    czy moja_gora - moj_dol == specjalne_premie[k]).
*/
void znajdz_premie(){
    REP(k, w){
        specjalne_premie[k] = 0;
        zastap[k] = false;
        for( int j = moja_gora; j < moj_dol; j++ )
            if( IsUsableCell(j, k) ) specjalne_premie[k]++;
            else{
                specjalne_premie[k] = 0;
                zastap[k] = true;
            }
    }
    if( myself != 0 ){
        Receive(myself - 1);
        REP(k, w){
            premie[k] = GetInt(myself - 1);
            if( zastap[k] == false )
                specjalne_premie[k] += premie[k];
        }
    }

    if( myself < NODES-1 ){
        REP(k, w) PutInt(myself + 1, specjalne_premie[k]);
        Send(myself + 1);
    }
}

inline LL komb(LL a){
    return a * (a+1) /2;
}

void znajdz_rozwa(){ //działkowa magia wykonana na każdym wierszu, na którym działa ten proces, wynik kumulowany w 0
    LL wynik = 0;
    stack<PI> propo;
    for( int j = moja_gora; j < moj_dol; j++ ){
        while(!propo.empty()) propo.pop();
        propo.push({-1, -1});
        REP(k, w){
            if( IsUsableCell(j, k) ) premie[k]++;
            else premie[k] = 0;
            int new_pos = k;
            while(propo.top().ST >= premie[k]){
                int old_height = propo.top().ST;
                int old_pos = propo.top().ND;
                propo.pop();
                int new_height = propo.top().ST;
                wynik += komb(k - old_pos) * (old_height-max(new_height, premie[k]));
                new_pos = old_pos;
            }
            propo.push({premie[k], new_pos});
        }
            premie[w] = 0;
            while(propo.top().ST > premie[w]){
                int old_height = propo.top().ST;
                int old_pos = propo.top().ND;
                propo.pop();
                int new_height = propo.top().ST;
                wynik += komb(w - old_pos) * (old_height-max(new_height, 0));
            }
    }

    PutLL(0, wynik);
    Send(0);

    LL real_wynik = 0;
    if( myself == 0 ){
        REP(i, NODES){
            Receive(i);
            real_wynik += GetLL(i);
        }
        cout << real_wynik << endl;
    }
}

int main(){
    h = GetFieldHeight();
    w = GetFieldWidth();
    NODES = NumberOfNodes();

    znajdz_zakres();
    znajdz_premie();

    znajdz_rozwa();

    return 0;
}