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

const int nax=75007;
const int max_mess_size=10000;

// nodesowe rzeczy
int nodes;
int mynode;

int pocz[nax];
int kon[nax];
int mydlu;
//koniec nodesowych rzeczy

int n, m;

bitset <nax> tab[1007];

int pra[nax];
int lew[nax];

long long wyn;

void calc()
{
	long long s=0;
	vector <int> wek;
	wek.push_back(m);
	for (int i=m-1; i>=0; i--)
	{
		while(pra[i]<pra[wek.back()])
		{
			s-=((long long)pra[wek.back()])*(wek[(int)wek.size()-2]-wek.back());
			wek.pop_back();
		}
		s+=((long long)pra[i])*(wek.back()-i);
		wek.push_back(i);
		wyn+=s;
	}
}

int main()
{
	nodes=NumberOfNodes();
	mynode=MyNodeId();
	
	n=GetFieldHeight();
	m=GetFieldWidth();
	
	nodes=min(nodes, n);
	
	if (mynode>=nodes)
		return 0;
	
	for (int i=0; i<nodes; i++)
		pocz[i]=i*(n/nodes);
	pocz[nodes]=n;
	
	for (int i=0; i<nodes; i++)
		kon[i]=pocz[i+1];
	
	mydlu=kon[mynode]-pocz[mynode];
	
	for (int i=pocz[mynode]; i<kon[mynode]; i++)
		for (int j=0; j<m; j++)
			tab[i-pocz[mynode]][j]=IsUsableCell(i, j);
	
	for (int i=0; i<m; i++)
		while(lew[i]<mydlu && tab[lew[i]][i])
			lew[i]++;
	
	if (mynode+1<nodes)
	{
		Receive(mynode+1);
		for (int i=0; i<m; i++)
		{
			pra[i]=GetInt(mynode+1);
			if (!(i%max_mess_size))
				Receive(mynode+1);
		}
	}
	
	for (int i=0; i<m; i++)
		if (lew[i]==mydlu)
			lew[i]+=pra[i];
	
	if (mynode)
	{
		for (int i=0; i<m; i++)
		{
			PutInt(mynode-1, lew[i]);
			if (!(i%max_mess_size))
				Send(mynode-1);
		}
		Send(mynode-1);
	}
	
	for (int i=mydlu-1; i>=0; i--)
	{
		for (int j=0; j<m; j++)
		{
			if (tab[i][j])
				pra[j]++;
			else
				pra[j]=0;
		}
		calc();
	}
	
	PutLL(0, wyn);
	Send(0);
	
	if (mynode)
		return 0;
	
	wyn=0;
	for (int i=0; i<nodes; i++)
	{
		Receive(i);
		wyn+=GetLL(i);
	}
	printf("%lld\n", wyn);
	
	return 0;
}