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
#include <bits/stdc++.h>

#include "dzialka.h"
#include "message.h"
using namespace std;

#define fru(j,n) for(int j=0; j<(n); ++j)
#define tr(it,v) for(auto it=(v).begin(); it!=(v).end(); ++it)
#define x first
#define y second
#define pb push_back
#define ALL(G) (G).begin(),(G).end()

#if 0
#define DEB printf
#else
#define DEB(...)
#endif

typedef long long ll;
typedef unsigned long long ull;
typedef long long LL;
typedef double D;
typedef pair<int,int> pii;
typedef vector<int> vi;

const int inft = 1000000009;
const int mod = 1000000007;
const int MAXN = 75005;

vi total,hi;

vector<pair<int,int> > V; //(wys, poz)
ull histogram(const vector<int>& E)
{
	ull ret=0;
	int n=E.size();
	fru(i,n)V[i]=make_pair(E[i],i);
	sort(ALL(V));
	set<int> S;
	S.insert(-1);S.insert(n);
	for(int i=0;i<n;i++){
		int u=V[i].x,he,wi;
		auto it=S.lower_bound(V[i].y);
		auto B=*it;
		it--;
		auto A=*it;
		wi=B-A-1;
		he=max((A>=0 && A<n)?E[A]:0,(B>=0 && B<n)?E[B]:0);
		DEB("param %d %d %d\n",wi,u,he);
		ret+=1LL*(u-he)*wi*(wi+1)/2;
		S.insert(V[i].y);
	}
	return ret;
}
/*
const int N=10000;
int GetFieldHeight(){
	return N;
}
int GetFieldWidth(){
	return N;
}
int IsUsableCell(int a,int b){
	return 1;
}*/

int main() {
	const int W=GetFieldWidth(),H=GetFieldHeight(),Nodes=NumberOfNodes();
	const int Id=MyNodeId();
	const int Chunk=(H+Nodes-1)/Nodes;
	V.resize(W);
	total.resize(W);hi.resize(W);
	// phase 0 get my rows
	const int sRow=Id*Chunk,eRow=min(H,(Id+1)*Chunk);
	if(sRow>=eRow){
		PutLL(0,0);
		Send(0);
		return 0;
	}
	DEB("Node %d ::[%d,%d)\n",Id,sRow,eRow);
	// phase 1 compute results for bottom
	fru(i,W){
		total[i]=0;
		for(int j=sRow;j<eRow;j++)if(IsUsableCell(j,i)){
			total[i]++;
		}else break;
	}
	//wait for the next node
	if(eRow!=H){
		Receive(Id+1);
		fru(i,W)hi[i]=GetInt(Id+1);
	}
	// send to the previous node
	if(Id){
		fru(i,W)if(total[i]==eRow-sRow)total[i]+=hi[i];
		fru(i,W)PutInt(Id-1,total[i]);
		Send(Id-1);
	}
	// phase 2 real computations
	ull Result=0;
	for(int j=eRow-1;j>=sRow;j--){
		fru(i,W){
			if(IsUsableCell(j,i))hi[i]++;else hi[i]=0;
		}
		//histogram
		ull Curr=histogram(hi);
		Result+=Curr;
	}
	// phase 3 merge results
	if(Id){
		PutLL(0,Result);
		Send(0);
	}
	else {
		int handled=1;
		while(handled<Nodes){
			int nr=Receive(-1);
			Result+=GetLL(nr);
			DEB("Received from %d\n",nr);
			handled++;
		}
		printf("%llu\n",Result);
	}

	return 0;
}