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