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
#include "message.h"
#include "dzialka.h"
#include <cstdio>
#include <stack>

using namespace std;

const int MAX_SIZE = 75001;

struct Pair {
    int col;
    int hei;
};

inline long long int possi(int n) {
    return (n % 2 == 0) ? (long long int)n/2*(n+1) : ((long long int)n+1)/2*n;
}

int height;
int width;
int hist[MAX_SIZE];
stack<Pair> st;

int main() {
    if (MyNodeId() == 0) {
        height = GetFieldHeight();
        width = GetFieldWidth();
        long long int total = 0;
        for (int r = 0; r < height; r++) {
            for (int c = 0; c < width; c++) {
                if (IsUsableCell(r, c) == 1) {
                    hist[c] += 1;
                } else {
                    hist[c] = 0;
                }
                
                int h = hist[c];
                int idx = c;
                
                if (!st.empty()) {
                    Pair t = st.top();
                    while (!st.empty() && t.hei > h) {
                        int th = t.hei;
                        idx = t.col;
                        st.pop();
                        int ph;
                        if (st.empty()) {
                            ph = h;
                        } else {
                            t = st.top();
                            ph = t.hei;
                            if (h > ph) ph = h;
                        }
                        long long int rects = possi(c-idx) * (th - ph);
                        total += rects;
                    }
                    if ((st.empty()) || (t.hei < h)) st.push({idx, h});
                } else {
                    if (h > 0) st.push({c, h});
                }
            }
            while (!st.empty()) {
                Pair t = st.top();
                int th = t.hei;
                int idx = t.col;
                st.pop();
                int ph;
                ph = st.empty() ? 0 : st.top().hei;
                long long int rects = possi(width-idx) * (th - ph);
                total += rects;
            }
        }
        printf("%lld\n", total);
    }
    return 0;
}