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
#include "dzialka.h"
#include "message.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int, int> PII;
const ll mod = 1000000007;
ll powmod(ll a, ll b) {ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) {if (b & 1)res = res * a % mod; a = a * a % mod;} return res;}
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;}
// head


const int N = 120, M = 75100;
int n, m, T, Z, b, b2, l1[N], r1[N], plen[M], prer[M], l2[N], r2[N];
int stk[M], top, pl[M], pr[M], vl[M], vr[M];
ll ret;
void gao() {
	int top = 0;
	rep(i, 0, m) {
		pl[i] = pr[i] = -1;
		int k = top;
		while (k > 0 && prer[stk[k - 1]] > prer[i]) --k;
		if (k) pr[stk[k - 1]] = i;
		if (k < top) pl[i] = stk[k];
		stk[k++] = i;
		top = k;
	}
	rep(i, 0, m) if (pl[i] == -1) vl[i] = i; else vl[i] = vl[pl[i]];
	per(i, 0, m) if (pr[i] == -1) vr[i] = i; else vr[i] = vr[pr[i]];
	rep(i, 0, m) ret += (ll)(i - vl[i] + 1) * (vr[i] - i + 1) * prer[i];
}

int main() {
	n = GetFieldHeight();
	m = GetFieldWidth();
	T = NumberOfNodes();
	Z = MyNodeId();
	b = (n + T - 1) / T;
	b2 = (m + T - 1) / T;
	rep(i, 0, T) l1[i] = min(i * b, n), r1[i] = min((i + 1) * b, n);
	rep(i, 0, T) l2[i] = min(i * b2, m), r2[i] = min((i + 1) * b2, m);
	rep(j, l2[Z], r2[Z]) {
		int len = 0;
		rep(i, 0, n) {
			plen[i] = len;
			if (IsUsableCell(i, j)) len++; else len = 0;
		}
		plen[n] = len;
		for (int i = 0; i < T; i++) PutInt(i, plen[l1[i]]);
	}
	rep(i, 0, T) Send(i);
	rep(i, 0, T) {
		Receive(i);
		rep(j, l2[i], r2[i]) prer[j] = GetInt(i);
	}
	for (int i = l1[Z]; i < r1[Z]; i++) {
		rep(j, 0, m) if (IsUsableCell(i, j)) prer[j]++; else prer[j] = 0;
		gao();
	}
	PutLL(0, ret);
	Send(0);
	if (Z == 0) {
		ll ans = 0;
		rep(i, 0, T) {
			Receive(i);
			ans += GetLL(i);
		}
		printf("%lld\n", ans);
	}
}