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

#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>
#include <assert.h>

using namespace std;

int main() {
	const int w = GetFieldWidth();
	const int h = GetFieldHeight();

	const int XB = w * MyNodeId() / NumberOfNodes();
	const int XE = w * (MyNodeId()+1) / NumberOfNodes();

	vector<int> L(h);
	vector<int> R(h);
	for (auto &r: R) r = INT_MAX;

	const int n_banks = 2;

	long long CCC = 0;
	vector<vector<int>> E;
	vector<int> P(h);
	fstream f;
	for (int bank = 0; bank < n_banks; bank++) {
		const int xb = XB + (XE - XB) * bank / n_banks;
		const int xe = XB + (XE - XB) * (bank + 1) / n_banks;

		E.resize(xe - xb);
		for (auto &C: E) {
			C.resize(h + 1);
			for (auto &c: C) c = INT_MIN;
		}

		for (int y = 0; y < h; y++) {
			int end = R[y];
			for (int x = XE - 1; x >= xb; x--) {
				if (!IsUsableCell(y, x)) end = x;
				if (xb <= x && x < xe) E[x-xb][y] = end;
			}
			if (bank == 0) L[y] = end;
		}


		if (bank == 0) {
			if (MyNodeId() == NumberOfNodes() - 1) {
				for (auto &r: R) r = w;
			} else {
				for (int y = 0; y < h; y++) {
					if (y % 1000 == 0) {
						int r = Receive(MyNodeId() + 1);
						assert(r == MyNodeId() + 1);
					}
					R[y] = GetInt(MyNodeId() + 1);
					assert(R[y] != INT_MAX);
				}
			}

			for (int y = 0; y < h; y++) {
				if (L[y] == INT_MAX) L[y] = R[y];
			}

			if (MyNodeId() != 0) {
				for (int y = 0; y < h; y++) {
					PutInt(MyNodeId() - 1, L[y]);
					if (y % 1000 == 999 || y == h - 1) Send(MyNodeId() - 1);
				}
			}
		}

#define RR(_y) ((EE[_y]) == INT_MAX ? R[_y] : EE[_y])
		for (int x = xb; x < xe; x++) {
			auto &EE = E[x-xb];
			long long CC = 0, C = 0;
			for (int y = h - 1; y >= 0; y--) {
				int z = y + 1;
				assert(RR(y) != INT_MIN);
				while (RR(z) >= RR(y)) {
					assert(RR(z) >= x);
					C -= (RR(z)-x) * (P[z] - z);
					z = P[z];
				}
				P[y] = z;
				assert(RR(y) >= x);
				C += (RR(y)-x) * (z - y);
				CC += C;
			}
			CCC += CC;
			f << "x = " << x << "; CC = " << CC << endl;
		}
	}

	if (MyNodeId() != 0) {
		PutLL(0, CCC);
		Send(0);
	} else {
		for (int n = NumberOfNodes() - 1; n > 0; n--) {
			vector<bool> R(NumberOfNodes());
			int r = Receive(-1);
			assert(r != MyNodeId());
			assert(!R[r]);
			long long C = GetLL(r);
			CCC += C;
			R[r] = true;
		}
		cout << CCC << endl;
	}
	return 0;
}