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
120
121
122
123
124
125
126
127
128
129
130
131
// PA2017, Krazki 2
// Andrzej Pezarski


#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <stack>


#include "message.h"
#include "dzialka.h"
//#include "dzialka.c"

using namespace std;


// int GetFieldHeight() {
//   return 75000;
// }
// 
// int GetFieldWidth() {
//   return 75000;
// }
// 
// int IsUsableCell(int r, int c) {
//   return r!=c?1:0;
// }
// 

#define MASTER_NODE 0

struct R
{
    stack <pair< pair<int, int>, long long > > S;
    int i;
    R() : i(0) {S.push(make_pair(make_pair(0, 0), 0LL));}
    long long operator()(int g)
    {
        int k=i;
        while(S.top().first.second>g) 
        {
            k=S.top().first.first;
            S.pop();
        }
        if(g!=0 && S.top().first.second!=g)
        {
            S.push(make_pair(make_pair(k, g), 1LL*k*(g-S.top().first.second)+S.top().second));
        }
        i++;
        return (1LL*i*g-S.top().second);
        
    }
};


long long cutPoint(long long i, long long N, long long M) {
    return i*(N/M)+min(i, N%M);
}

int main() {
    long long N=GetFieldHeight();
    long long M=GetFieldWidth();
    long long nodes=NumberOfNodes();
    long long my_id=MyNodeId();
    
    long long firstN = cutPoint(my_id, N, nodes);
    long long lastN = cutPoint(my_id+1, N, nodes);
    
    long long firstM = cutPoint(my_id, M, nodes);
    long long lastM = cutPoint(my_id+1, M, nodes);
    
    long long myN = lastN-firstN;
    long long myM = lastM-firstM;

    vector <int> G(M, 0);
    for (int i=0; i<nodes; i++) {
        PutLL(i, myM);
        for (int m=firstM; m<lastM; m++) {
            PutInt(i, G[m]);
        }
        Send(i);
        int fN = cutPoint(i, N, nodes);
        int lN = cutPoint(i+1, N, nodes);
        for (int n=fN; n<lN; n++) {
            for (int m=firstM; m<lastM; m++) {
                G[m]=IsUsableCell(n, m)? G[m]+1 : 0;
            }
        }
    }
    G.clear();
    for (int i=0; i<nodes; i++) {
        Receive(i);
        long long tempM=GetLL(i);
        while(tempM--) {
            G.push_back(GetInt(i));
        }
    }
    
    long long result=0LL;
    for (int n=firstN; n<lastN; n++) {
        R r;
        for (int m=0; m<M; m++) {
            G[m]=IsUsableCell(n, m)? G[m]+1 : 0;
//            printf("%d\n", G[m]);
            result+=r(G[m]);
        }
        result+=r(0);
    }
    
   
//        printf("%lld\n", result);
    
    if (my_id == 0) {
        for (int i=1; i<nodes; i++){
            Receive(i);
            result+=GetLL(i);
        }
        printf("%lld\n", result);
//        cout << result;
    } else {
        PutLL(0, result);
        Send(0);
    }
    
    return 0;
}