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<cstdio>
#include<iostream>
#include<sstream>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<list>
#include<vector>
#include<stack>
#include<queue>
#include<string>
#include<iomanip>
#include<fstream>
#include<ctime>
#include <functional>
#include <pthread.h>
#include <unistd.h>
#include <thread>
#include <mutex> 
#include "dzialka.h"
#include "message.h"
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
typedef pair <ii, LL> iil;
#define pb push_back
const int INF = 2147483647;

using namespace std;

int noOfRowsForMessage = 1000;

int getNoOfColumns(int nodeId, int width, int noOfNodes) {
	int noOfColumns = width / noOfNodes;
	if (width % noOfNodes > nodeId) noOfColumns++;
	return noOfColumns;
}

int find(int bound, vector<iil> &specWek) {
	int l = 0;
	int r = specWek.size() - 1;
	int mid;
	while (l < r) {
		mid = (l + r) / 2;
		if (specWek[mid].first.first <= bound) l = mid + 1; else r = mid;
	}
	if (specWek[l].first.first > bound) return l;
	return -1;
}

int main() {
	int i, j, k, last, minn, use, ind;
	int nodeId = MyNodeId();
	int noOfNodes = NumberOfNodes();
	int height = GetFieldHeight();
	int width = GetFieldWidth();
	int noOfColumns = getNoOfColumns(nodeId, width, noOfNodes);
	if (noOfColumns == 0) return 0;
	vector<iil> wek[noOfColumns];	
	vector<iil> specWek;
	int startColumn = 0;
	for (i = 0;i < nodeId;i++) startColumn += getNoOfColumns(i, width, noOfNodes);
	for (i = 0;i < noOfColumns;i++) wek[i].pb(iil(ii(-1, startColumn + i), 0));
	specWek.pb(iil(ii(-1, startColumn - 1), 0));
	LL res = 0, locRes;
	for (i = 0;i < height;i++) {
		if (i % noOfRowsForMessage == 0 && startColumn != 0) Receive(nodeId - 1);
		last = startColumn == 0 ? -1 : GetInt(nodeId - 1);
		while (specWek.size() > 0 && specWek.back().first.second <= last) specWek.pop_back();
		locRes = 0;
		if (last != startColumn - 1) locRes = (startColumn - 1 - last) * 1LL * (i - specWek.back().first.first) + specWek.back().second;
		specWek.push_back(iil(ii(i, last), locRes));
		for (j = startColumn;j < startColumn + noOfColumns;j++) {
			use = IsUsableCell(i, j);
			if (!use) last = j;
			if (last >= startColumn) {
				while (wek[j - startColumn].size() > 0 && wek[j - startColumn].back().first.second <= last) {
					wek[j - startColumn].pop_back();
				}
			}
			locRes = 0;
			if (use) {
				if (last >= startColumn) {
					locRes += (j - last) * 1LL * (i - wek[j - startColumn].back().first.first);
					locRes += wek[j - startColumn].back().second;
				} else {
					ind = find(wek[j - startColumn].back().first.first, specWek);
					if (ind == -1) {
						locRes += (j - last) * 1LL * (i - wek[j - startColumn].back().first.first);
						locRes += wek[j - startColumn].back().second;
					} else {
						locRes += (specWek.back().second - specWek[ind].second);
						locRes += (j - startColumn + 1) * 1LL * (i - specWek[ind].first.first);
						locRes += (j - specWek[ind].first.second) * 1LL * (specWek[ind].first.first - wek[j - startColumn].back().first.first);
						locRes += wek[j - startColumn].back().second;
					}
				}			
			}
			if (last >= startColumn) wek[j - startColumn].push_back(iil(ii(i, last), locRes));
			res += locRes;
		}
		if (startColumn + noOfColumns < width) PutInt(nodeId + 1, last);
		if (i == height - 1) {
			if (startColumn != 0) res += GetLL(nodeId - 1);
			if (startColumn + noOfColumns < width) PutLL(nodeId + 1, res); else printf("%lld\n", res);
		}		
		if ((i % noOfRowsForMessage == noOfRowsForMessage - 1 || i == height - 1) && (startColumn + noOfColumns < width)) {
			Send(nodeId + 1);
		}
	}	
}