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
#include "dzialka.h"
#include "message.h"
#include <iostream>
#include <vector>


int main() {
	int MAXX = GetFieldHeight();
	int MAXY = GetFieldWidth();
	int NODES = NumberOfNodes();
	int MYID = MyNodeId();
	int starty = MYID*MAXY/NODES;
	int endy = (MYID+1)*MAXY/NODES;
	unsigned long long int result = 0;

	std::vector<int> cnt(MAXX,0);
	std::vector<int> height(MAXX,0);

	if (MYID != NODES-1) {
		for (int x=0; x<MAXX; ++x) {
			int y = endy-1;
			while (y>=starty && IsUsableCell(x,y)) {
				cnt[x]++;
				y--;
			}
		}
	}

	if (MYID != 0) {
		int target = endy-starty;
		for (int x=0; x<MAXX; ++x) {
			if (x%2000==0) {
				Receive(MYID-1);
			}
			height[x] = GetInt(MYID-1);
			if (cnt[x]==target) {
				cnt[x] += height[x];
			}
		}
	}

	if (MYID != NODES-1) {
		for (int x=0; x<MAXX; ++x) {
			PutInt(MYID+1, cnt[x]);
			if (x%2000==1999) {
				Send(MYID+1);
			}
		}
		if ((MAXX-1)%2000!=1999) {
			Send(MYID+1);
		}
	}

	std::vector<std::pair<int, int> > hstack(MAXX+10);
	for (int y=starty; y<endy; ++y) {
		unsigned long long int vertexes=0;
		int hspos=0;
		hstack[hspos++] = std::make_pair(-1,-1);

		for (int x=0; x<MAXX; ++x) {
			if (IsUsableCell(x,y)) {
				height[x]++;
			} else {
				height[x]=0;
			}

			int lastx = x;
			while (hstack[hspos-1].second > height[x]) {
				vertexes -= ((unsigned long long int)(hstack[hspos-1].second-height[x]))*(lastx-hstack[hspos-1].first);
				lastx = hstack[hspos-1].first;
				hspos--;
			}
			hstack[hspos++] = std::make_pair(lastx, height[x]);
			vertexes += height[x];
			result += vertexes;

		}
	}

	if (MYID != 0) {
		PutLL(0,result);
		Send(0);
	} else {
		for (int i=1; i<NODES; ++i) {
			Receive(i);
			unsigned long long int part = GetLL(i);
			result += part;
		}
		std::cout << result << std::endl;
	}
	return 0;
}