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
114
115
116
117
118
119
#include "dzialka.h"
#include "message.h"

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

#define fru(j,n) for(int j=0; j<(n); ++j)
#define tr(it,v) for(auto it=(v).begin(); it!=(v).end(); ++it)
#define x first
#define y second
#define pb push_back
#define ALL(G) (G).begin(),(G).end()

//#define DEBUG
#ifdef DEBUG
#define DEB printf
#else
#define DEB(...)
#endif

typedef long long LL;
typedef pair<int,int> pii;
typedef vector<int> vi;

int ja,hei,wid,h0,h1,w0,w1;
LL teraz;

const int MAXN=75005;
const int NODES=100;
const int BAS=1<<17;
vi to_send[NODES];

int E[BAS];
int D[2*BAS];

inline int lepszy(int a, int b){return E[a]<E[b]?a:b;}

int get_min(int a,int b){
	 int ret=lepszy(a,b);
	 a+=BAS;
	 b+=BAS;
	 while(a/2!=b/2){
		  if((a&1)==0) ret=lepszy(ret,D[a+1]);
		  if((b&1)==1) ret=lepszy(ret,D[b-1]);
		  a>>=1;
		  b>>=1;
	 }
	 return ret;
}

void go(int a, int b){
	 if(a>b) return;
	 int p=get_min(a,b);
	 teraz+=1LL*E[p]*(b-p+1)*(p-a+1);
	 go(a,p-1);
	 go(p+1,b);
}

LL licz(){
	 teraz=0;
	 for(int i=BAS-1;i;--i)
		  D[i]=lepszy(D[i*2],D[i*2+1]);
	 int last_0=-1;
	 fru(i,wid) if(E[i]==0){
		  if(last_0+1<i) go(last_0+1,i-1);
		  last_0=i;
	 }
	 go(last_0+1,wid-1);
	 return teraz;
}

int main(){
	 fru(i,BAS) D[i+BAS]=i;
	 ja=MyNodeId();
	 hei=GetFieldHeight();
	 wid=GetFieldWidth();
	 int nodes=NumberOfNodes();
	 assert(0<=ja && ja<nodes);
	 int hj=(hei+nodes-1)/nodes;
	 h0=hj*ja;
	 h1=min(hei,hj*(ja+1));
	 int wj=(wid+nodes-1)/nodes;
	 w0=wj*ja;
	 w1=min(wid,wj*(ja+1));
	 for(int c=w0;c<w1;++c){
		  int q=0;
		  fru(r,hei){
				if(IsUsableCell(r,c)) ++q;
				else q=0;
				if(r%hj==0) to_send[r/hj].pb(q);
		  }
	 }
	 fru(i,nodes){
		  tr(it,to_send[i]) PutInt(i,*it);
		  Send(i);
	 }
	 fru(i,nodes) Receive(i);
	 if(h0<h1) fru(i,wid) E[i]=GetInt(i/wj);
	 LL ret=0;
	 for(int r=h0;r<h1;++r){
		  if(r!=h0){
				fru(c,wid) if(IsUsableCell(r,c)) ++E[c];
				else E[c]=0;
		  }
		  LL q=licz();
		  ret+=q;
	 }
	 PutLL(0,ret);
	 Send(0);
	 if(ja==0){
		  LL wynik=0;
		  fru(i,nodes){
				Receive(i);
				wynik+=GetLL(i);
		  }
		  printf("%lld\n",wynik);
	 }
	 return EXIT_SUCCESS;
}