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
#include<bits/stdc++.h>
#include "dzialka.h"
#include "message.h"
#define ll  long long
#define pb push_back
#define MP make_pair

using namespace std;

int curr[ 80000 ];
vector< ll > stos;

int t[ 80000 ];
vector< pair< int , int > > wysokosci;
int dlugosc[ 80000 ];
int s[ 80000];
ll sumeczka = 0;

int Find( int x )
{
	if( t[ x ] == x ) return x;
	else return t[ x ] = Find( t[ x ] );
}

void Union( int a , int b )
{
	ll x1 = dlugosc[ Find( b ) ] , x2 = dlugosc[ Find( a ) ];
	//cout << b << " lacze z " << a << endl;
	sumeczka -= ( x1 * ( x1 + 1 ) ) / 2 + ( x2 * ( x2 + 1 ) ) / 2;
	t[ Find( b ) ] = Find( a );
	dlugosc[ Find( a ) ] = x1 + x2;
	sumeczka += ( ( x1 + x2 ) * ( x1 + x2 + 1 ) ) / 2;
}

int main()
{
    int h = GetFieldHeight() , w = GetFieldWidth();
    int n = min( min( h , w ) , NumberOfNodes() );
    int v = MyNodeId();

    if( v < n )
    {
        int a = v * w / n , b = ( v + 1 ) * w / n - 1;
        int wsk = 0;
        for( int i = 0 ; i < h ; i++ )
        {
            if( i == wsk * h / n )
            {
                for( int j = a ; j <= b ; j++ ) PutInt( wsk , s[ j ] );
                Send( wsk );
                wsk++;
            }
            for( int j = a ; j <= b ; j++ )
            {
                if( IsUsableCell( i , j ) ) s[ j ]++;
                else s[ j ] = 0;
            }
        }



        for( int u = 0 ; u < n ; u++ )
        {
            Receive( u );
            for( int j = u * w / n ; j <= ( u + 1 ) * w / n - 1 ; j++ ) curr[ j ] = GetInt( u );
        }

        int pocz = v * h / n , konc = ( v + 1 ) * h / n - 1;
        ll ans = 0 , partiarazem = 0;
        for( int i = pocz ; i <= konc ; i++ )
        {
            for( int j = 0 ; j < w ; j++ )
            {
                if( IsUsableCell( i , j ) ) curr[ j ]++;
                else curr[ j ] = 0;
            }
            for( int j = 0 ; j < w ; j++ ) if( curr[ j ] != 0 ) wysokosci.pb( MP( curr[ j ] , j ) );
		sort( wysokosci.begin() , wysokosci.end() );
		for( int se = wysokosci.size() - 1 ; se >= 0 ; se += 0 )
		{
			ll wys = wysokosci[ se ].first;
			while( i >= 0 && wysokosci[ se ].first == wys )
			{
				int ind = wysokosci[ se ].second;
				dlugosc[ ind ] = 1;
				t[ ind ] = ind;	
				sumeczka++;
				if( dlugosc[ ind + 1 ] != 0 ) Union( ind , ind + 1 );
				if( ind != 0 && dlugosc[ ind - 1 ] != 0 ) Union( ind , ind - 1 );		
				se--;
			}
			if( se == -1 ) ans += wys * sumeczka;
			else
			{
				partiarazem = wysokosci[ se ].first;
				ans += ( wys - partiarazem ) * sumeczka;			
			}
		}
		if( i != konc ){
		for( int j = 0 ; j < w ; j++ ) dlugosc[ j ] = 0;
		wysokosci.clear();
		sumeczka = 0;}
        }
        PutLL( 0 , ans );
        Send( 0 );
        if( v == 0 )
        {
		ans = 0;
            for( int i = 0 ; i < n ; i++ )
            {
                Receive( i );
                ans += GetLL( i );
            }
            cout << ans;
        }
    }

	return 0;
}