#include "message.h"






#include "dzialka.h"















#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using Pii = pair<int,int>;

int ri() { int x; scanf("%d",&x); return x; }
ll rll() { ll x; scanf("%lld",&x); return x; }

void print(int x) { printf("%d",x); }
void print(ll x) { printf("%lld",x); }

template<class T> void remin(T& var, T x) { var = min(var,x); }
template<class T> void remax(T& var, T x) { var = max(var,x); }


#define REP(i,n) for(int i=0; i<int(n); ++i)
#define PER(i,n) for(int i=(n)-1; i>=0; --i)

#define FOR(i,a,b) for(int i=(a); i<int(b); ++i)
#define ROF(i,a,b) for(int i=(b)-1; i>=int(a); --i)

#define ALL(c) (c).begin(), (c).end()



ll randll() {
	ll r = 0;
	REP(i,5) {
		r ^= rand();
		r <<= 15;
	}
	return abs(r);
}

ll rand(ll a, ll b) {
	return a + randll()%(b-a);
}

#define DBG false











const int MAX_H = 750 * 1000 + 10;
int last[MAX_H];







struct Point {
	int y;
	int x;
};

Point points[MAX_H+10];
int num_points = 0;






int NUM_NODES = NumberOfNodes();
const int ME = MyNodeId();

const int H = GetFieldHeight();
const int W = GetFieldWidth();






inline int get_x0(int node) {
	return node * W / NUM_NODES;
}


inline int get_x1(int node) {
	int x1 = (node+1) * W / NUM_NODES;

	if(node == NUM_NODES-1) x1 = W;

	return x1;
}



inline int get_y0(int node) {
	return node * H / NUM_NODES;
}

inline int get_y1(int node) {
	int y1 = (node+1) * H / NUM_NODES;

	if(node == NUM_NODES-1) y1 = H;

	return y1;
}





int main() {

	if(NUM_NODES > W) {
		NUM_NODES = W;
	}

	if(ME >= NUM_NODES) return 0;

	int x0 = get_x0(ME);
	int x1 = get_x1(ME);

	// compute last element in each row

	int y0 = get_y0(ME);
	int y1 = get_y1(ME);

	FOR(y,y0,y1) {
		int curr_last = -1;

		REP(cnode, NUM_NODES-1) {
			int xx0 = get_x0(cnode);
			int xx1 = get_x1(cnode);

			FOR(x, xx0, xx1) {
				if(!IsUsableCell(y,x)) curr_last = x;
			}

			PutInt(cnode+1, curr_last);
		}
	}

	if(y0 < y1) REP(cnode, NUM_NODES-1) {
		Send(cnode+1);
	}




	if(ME == 0) {
		REP(y,H) last[y] = -1;
	}
	else {
		REP(cnode, NUM_NODES) {
			Receive(cnode);

			int yy0 = get_y0(cnode);
			int yy1 = get_y1(cnode);

			FOR(y, yy0, yy1) {
				last[y] = GetInt(cnode);
			}
		}
	}




	if(DBG) {
		fprintf(stderr, "INPUT:\n");
		REP(y,H) {
			REP(x,W) {
				fprintf(stderr, "%d", IsUsableCell(y,x));
			}
			fprintf(stderr, "\n");
		}
	}




	// now `last` has valid values



	ll total = 0;


	vector<ll> dbg;


	// dp
	FOR(x, x0, x1) {
		ll val = 0;

		num_points = 1;
		points[0] = {-1,x};

		REP(y,H) {
			if(IsUsableCell(y,x)) {
				while(points[num_points-1].x <= last[y]) {
					auto diff = 1LL * (last[y] - points[num_points-1].x) * (points[num_points-1].y - points[num_points-2].y);
					val -= diff;
					--num_points;
				}

				val += x - last[y];

				points[num_points++] = {y, last[y]};
			}
			else {
				val = 0;
				last[y] = x;

				num_points = 1;
				points[0] = {y, x};
			}

			//fprintf(stderr, "result[%d][%d] == %lld\n", y, x, val);

			//fprintf(stderr, "%lld\t", val);

			if(DBG) dbg.push_back(val);

			total += val;
		}

		//fprintf(stderr, "\n");
	}




	if(ME == 0) {
		FOR(i, 1, NUM_NODES) {
			Receive(i);
			total += GetLL(i);
		}
		printf("%lld", total);

		if(DBG) {
			REP(y,H) {
				REP(x,W) {
					fprintf(stderr, "%lld\t", dbg[x*H + y]);
				}
				fprintf(stderr, "\n");
			}
		}
	}
	else {
		PutLL(0, total);
		Send(0);
	}
}