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

/*int IsUsableCell(int r, int c) {
	return r!=c ? 1 : 0;
}

int GetFieldHeight() {
	return 75000;
}

int GetFieldWidth() {
	return 75000;
}*/

void count_verts(std::vector<int>& t, int begin_row, int end_row, int m) {
	for (int j = 0; j < m; j++) {
		for (int i = begin_row; i < end_row; i++) {
			int c = IsUsableCell(i, j);
			if (!c) t[j] = 0;
			else ++t[j];
		}
	}
}

const int M = 75013;

int sh[M], sc[M];

long long count(std::vector<int>& t, int begin_row, int end_row, int m) {
	long long ret = 0;
	for (int i = begin_row; i < end_row; i++) {
		int s = 1;
		sh[0] = sc[0] = 0;
		long long sum = 0;
		for (int j = m-1; j >= 0; j--) {
			int c = IsUsableCell(i, j);
			if (!c) t[j] = 0;
			else ++t[j];
			int x = 1;
			while (s > 0 && sh[s-1] >= t[j]) {
				s--;
				sum -= ((long long)sh[s]) * sc[s];
				x += sc[s];
			}
			sh[s] = t[j];
			sc[s] = x;
			sum += ((long long)t[j]) * x;
			s++;
			//printf("%d %d :: %lld\n",i,j,sum);	
			ret += sum;
		}
	}
	return ret;
}

int main() {
	int num_nodes = NumberOfNodes();
	int my_id = MyNodeId();
	int n = GetFieldHeight();
	int m = GetFieldWidth();
	int begin_row = n * my_id / num_nodes;
	int end_row = n * (my_id + 1) / num_nodes;
	std::vector<int> my_verts(m);
	count_verts(my_verts, begin_row, end_row, m);
	std::vector<int> up(m);
	const int SHARDS = std::min(300, m);
	for (int k = 0; k < SHARDS; k++) {
		int begin_col = m * k / SHARDS;
		int end_col = m * (k+1) / SHARDS;
		if (my_id > 0) {
			Receive(my_id - 1);
			for (int j = begin_col; j < end_col; j++)
				up[j] = GetInt(my_id - 1);
		}
		for (int j = begin_col; j < end_col; j++) {
			if (my_verts[j] == end_row - begin_row)
				my_verts[j] += up[j];
		}
		if (my_id < num_nodes - 1) {
			for (int j = begin_col; j < end_col; j++)
				PutInt(my_id + 1, my_verts[j]);
			Send(my_id + 1);
		}
	}
	long long sum = count(up, begin_row, end_row, m);	
	if (my_id < num_nodes - 1) {
		PutLL(num_nodes - 1, sum);
		Send(num_nodes - 1);
	} else {
		for (int i = 0; i < num_nodes - 1; i++) {
			int v = Receive(-1);
			sum += GetLL(v);
		}
		printf("%lld\n", sum);
	}
	return 0;
}