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;
}
|