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
#include <iostream>

#include "message.h"
#include "dzialka.h"

using namespace std;

typedef unsigned long long u64;
const int MAX = 75001;
u64 G[MAX], aG[MAX];
struct _sums {
	_sums():x(0),G(0),s(0){}
	_sums(u64 _G,u64 _s, u64 _x):x(_x),G(_G),s(_s) {
		//printf("%lld %lld %lld\n", x,G,s);
	}
	u64 x; // najbardziejszy w prawo o tej wysokosci
	u64 G; // wysokosc wszystkich prostokatow konczacych sie w w tej linii na pozycji x
	u64 s; // liczba wszystkich prostokatow mozliwych do zbudowania
} s[MAX];

u64 size;
_sums& top() {return s[size-1];}
void push(const _sums& a) {s[size++]=a;}
void pop() {size--;}

u64 update_sums(u64 y, u64 x, u64 g){
//	y++;
	x++;
	if (size == 0) {
		push(_sums(0,0,0));
	}
	if (g>=top().G) {
		push(_sums(g, top().s+g, x));
	} else {
		while (size>0 && g<top().G)
			pop();
		push(_sums(g,top().s + (x-top().x) * g, x));
	}
//	printf("%lld %lld %lld %lld\n", y, x, g, top().s);
	return top().s;
}

int main() {
	u64 h,w,y,x,n,k,start,chunk;
	h = GetFieldHeight();
	w = GetFieldWidth();
	n = NumberOfNodes();
	k = MyNodeId();

	if ((h*w<1000000) || h<n) {
		n = 1;
		k = 0;
	}

	u64 lowy = (h * k)/n, highy = (h * (k+1))/n; u64 wynik=0;

	if (n>1) {
		chunk = 500;
		for (start=0; start<w; start += chunk) {
			if (k>0)
				Receive(k-1);
			for (x=start; x<w && x<start+chunk; x++) {
				if (k>0)
					G[x] = aG[x] = GetInt(k-1);
				for (y=lowy; y<highy; y++)
					aG[x] = IsUsableCell(y,x) ? aG[x]+1 : 0;
				if (k<n-1)
					PutInt(k+1, aG[x]);
			}
			if (k<n-1)
				Send(k+1);
		}
	}
	if (k==MyNodeId()) {
		for (y=lowy; y<highy; y++) {
			for (x=0; x<w; x++)
				wynik += update_sums(y, x, G[x] = IsUsableCell(y,x) ? G[x]+1 : 0);
			size = 0;
		}
	}
	if (n>1) {
		if (k==0) {
			for (x=1; x<n; x++) {
				Receive(x);
				wynik += GetLL(x);
			}	
		} else {
			PutLL(0, wynik);
			Send(0);
		}
	}

	if (MyNodeId()==0)
		printf("%lld\n", wynik);

	return 0;
}