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
#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 = 100;

int h;
int w;

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

int przedzial;
int moja_gora;
int moj_dol;

void znajdz_zakres(){
    przedzial = (h / NODES) + 1;
    moja_gora = MyNodeId() * przedzial;
    moj_dol = min((MyNodeId() + 1) * przedzial, h);
}

void znajdz_premie(){
    REP(k, w){
		//cout << k << endl;
        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;
            }
    }
//cout << "PIERWSZE" << endl;
    if( MyNodeId() != 0 ){
        Receive(MyNodeId() - 1);
        REP(k, w){
            premie[k] = GetInt(MyNodeId() - 1);
            if( zastap[k] == false )
                specjalne_premie[k] += premie[k];
        }
    }

    if( MyNodeId() < NODES-1 ){
        REP(k, w) PutInt(MyNodeId() + 1, specjalne_premie[k]);
        Send(MyNodeId() + 1);
    }
//cout << "WYSLANE" << endl;
}

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

void znajdz_rozwa(){
    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));
            }
    }
//cout << "ZNALAZLEM" << endl;
    PutLL(0, wynik);
    Send(0);

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

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

    znajdz_zakres();
    znajdz_premie();

    znajdz_rozwa();

    return 0;
}