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
#include "message.h"
#include "dzialka.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;}
const int nodes = NumberOfNodes();
const int myid = MyNodeId();
template <typename T> T split(T n, T i, T tot) {
	return n / tot * i + min(i, n % tot);
}

const int N = 120, M = 75100;
int n, m, 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();
	rep(i, 0, nodes) l1[i] = split(n,i,nodes), r1[i] =split(n,i+1,nodes);
	rep(i, 0, nodes) l2[i] = split(m,i,nodes), r2[i]=split(m,i+1,nodes);
	rep(j, l2[myid], r2[myid]) {
		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 < nodes; i++) PutInt(i, plen[l1[i]]);
	}
	rep(i, 0, nodes) Send(i);
	rep(i, 0, nodes) {
		Receive(i);
		rep(j, l2[i], r2[i]) prer[j] = GetInt(i);
	}
	for (int i = l1[myid]; i < r1[myid]; i++) {
		rep(j, 0, m) if (IsUsableCell(i, j)) prer[j]++; else prer[j] = 0;
		gao();
	}
	PutLL(0, ret);
	Send(0);
	if (myid == 0) {
		ll ans = 0;
		rep(i, 0, nodes) {
			Receive(i);
			ans += GetLL(i);
		}
		printf("%lld\n", ans);
	}
}