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
// Przykładowe (błędne) rozwiązanie - każdy węzeł wysyła węzłowi o numerze 0
// pierwszą z cen swoich akcji. Węzeł 0 wypisuje sumę tych liczb.
#include "message.h"
#include "dzialka.h"

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <bitset>
#include <cassert>
using namespace std;
int L[76000],R[76000],totm,n,m,myid,M,head,N;
int s[76000],where[76000];
long long sum;
/*  return 30000;
}
int GetFieldWidth() {
  return 40000;
}
int IsUsableCell(int x, int y) {
  return ((long long )x*3454677^y)%1000000007%100!=0;
}*/
int Lborder[10000],Uborder[10000];
int main() {
  totm=NumberOfNodes();
  N=GetFieldHeight();
  M=GetFieldWidth();
  myid=MyNodeId();
  int n=N/totm;
  int m=M/totm;
  for (int i=0;i<totm;i++){
    if (i<M%totm) Lborder[i+1]=m+1; else Lborder[i+1]=m;
    if (i<N%totm) Uborder[i+1]=n+1; else Uborder[i+1]=n;
  }
  for (int i=1;i<=totm;i++){
    Lborder[i]+=Lborder[i-1]; Uborder[i]+=Uborder[i-1];
  }
  n=Uborder[myid+1]-Uborder[myid];
  m=Lborder[myid+1]-Lborder[myid];
  //cout<<"fa "<<myid<<" "<<n<<" "<<m<<" "<<N<<" "<<M<<" "<<Lborder[myid]<<" "<<Uborder[myid]<<endl;
  int now=0;
  for (int i=0;i<M;i++){
    while (now<totm&&i==Lborder[now]){
      for (int j=0;j<n;j++){
        PutInt(now,L[j]); 
      }
      Send(now);
      now++;
    }
    for (int j=0;j<n;j++){
      int x=Uborder[myid]+j;
      int y=i;
      if (IsUsableCell(x,y)) L[j]++; else L[j]=0;
    }
    //cout<<"fa "<<myid<<" "<<i<<endl;
    //for (int j=0;j<n;j++) cout<<L[j]<<" "; cout<<endl;
  }
  //cout<<"end "<<myid<<endl;
  while (now<totm&&M==Lborder[now]){
    for (int j=0;j<n;j++){
      PutInt(now,L[j]); 
    }
    Send(now);
    now++;
  }

  for (int i=0;i<totm;i++){
    Receive(i);
    for (int j=Uborder[i];j<Uborder[i+1];j++)
      L[j+1]=GetInt(i);
  }

  //cout<<"myid "<<myid<<endl;
  //for (int i=1;i<=N;i++) cout<<L[i]<<" "; cout<<endl;
  //cout<<"end2 "<<myid<<endl;
  long long ans=0; 
  for (int now=1;now<=m;now++){
    for (int i=1;i<=N;i++)
      if (IsUsableCell(i-1,now-1+Lborder[myid])==0){
       // cout<<"forbid "<<i-1<<" "<<now-1+Lborder[myid]<<endl;
        L[i]=0;
      } else L[i]++;
    head=0; s[0]=0; where[0]=0;
    sum=0;
    //cout<<"calc "<<myid<<" "<<now<<endl;
    //cout<<"asd "<<myid<<" "<<now<<endl;
    //for (int i=1;i<=N;i++) cout<<L[i]<<" "; cout<<endl;
    for (int i=1;i<=N;i++){
      while (head&&s[head]>=L[i]){
        sum-=1ll*(where[head]-where[head-1])*s[head];
        head--;
      }
      head++; s[head]=L[i]; where[head]=i;
      sum+=1ll*(where[head]-where[head-1])*s[head];
      ans+=sum;
    //  cout<<"calc "<<myid<<" "<<i<<" "<<now<<" "<<ans<<endl;
    //  for (int j=1;j<=head;j++) cout<<where[j]<<" "<<s[j]<<endl;
    }
  }
  if (myid==totm-1){
    for (int i=0;i<myid;i++){
      Receive(i);
      ans+=GetLL(i);
    }
    cout<<ans<<endl;
  } else {
    PutLL(totm-1,ans);
    Send(totm-1);
  }
  return 0;
}