#include "dzialka.h" #include "message.h" #include <cstdio> #include <vector> /*int IsUsableCell(int r, int c) { return r!=c ? 1 : 0; } int GetFieldHeight() { return 75000; } int GetFieldWidth() { return 75000; }*/ void count_verts(std::vector<int>& t, int begin_row, int end_row, int m) { for (int j = 0; j < m; j++) { for (int i = begin_row; i < end_row; i++) { int c = IsUsableCell(i, j); if (!c) t[j] = 0; else ++t[j]; } } } const int M = 75013; int sh[M], sc[M]; long long count(std::vector<int>& t, int begin_row, int end_row, int m) { long long ret = 0; for (int i = begin_row; i < end_row; i++) { int s = 1; sh[0] = sc[0] = 0; long long sum = 0; for (int j = m-1; j >= 0; j--) { int c = IsUsableCell(i, j); if (!c) t[j] = 0; else ++t[j]; int x = 1; while (s > 0 && sh[s-1] >= t[j]) { s--; sum -= ((long long)sh[s]) * sc[s]; x += sc[s]; } sh[s] = t[j]; sc[s] = x; sum += ((long long)t[j]) * x; s++; //printf("%d %d :: %lld\n",i,j,sum); ret += sum; } } return ret; } int main() { int num_nodes = NumberOfNodes(); int my_id = MyNodeId(); int n = GetFieldHeight(); int m = GetFieldWidth(); int begin_row = n * my_id / num_nodes; int end_row = n * (my_id + 1) / num_nodes; std::vector<int> my_verts(m); count_verts(my_verts, begin_row, end_row, m); std::vector<int> up(m); const int SHARDS = std::min(300, m); for (int k = 0; k < SHARDS; k++) { int begin_col = m * k / SHARDS; int end_col = m * (k+1) / SHARDS; if (my_id > 0) { Receive(my_id - 1); for (int j = begin_col; j < end_col; j++) up[j] = GetInt(my_id - 1); } for (int j = begin_col; j < end_col; j++) { if (my_verts[j] == end_row - begin_row) my_verts[j] += up[j]; } if (my_id < num_nodes - 1) { for (int j = begin_col; j < end_col; j++) PutInt(my_id + 1, my_verts[j]); Send(my_id + 1); } } long long sum = count(up, begin_row, end_row, m); if (my_id < num_nodes - 1) { PutLL(num_nodes - 1, sum); Send(num_nodes - 1); } else { for (int i = 0; i < num_nodes - 1; i++) { int v = Receive(-1); sum += GetLL(v); } printf("%lld\n", sum); } 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 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | #include "dzialka.h" #include "message.h" #include <cstdio> #include <vector> /*int IsUsableCell(int r, int c) { return r!=c ? 1 : 0; } int GetFieldHeight() { return 75000; } int GetFieldWidth() { return 75000; }*/ void count_verts(std::vector<int>& t, int begin_row, int end_row, int m) { for (int j = 0; j < m; j++) { for (int i = begin_row; i < end_row; i++) { int c = IsUsableCell(i, j); if (!c) t[j] = 0; else ++t[j]; } } } const int M = 75013; int sh[M], sc[M]; long long count(std::vector<int>& t, int begin_row, int end_row, int m) { long long ret = 0; for (int i = begin_row; i < end_row; i++) { int s = 1; sh[0] = sc[0] = 0; long long sum = 0; for (int j = m-1; j >= 0; j--) { int c = IsUsableCell(i, j); if (!c) t[j] = 0; else ++t[j]; int x = 1; while (s > 0 && sh[s-1] >= t[j]) { s--; sum -= ((long long)sh[s]) * sc[s]; x += sc[s]; } sh[s] = t[j]; sc[s] = x; sum += ((long long)t[j]) * x; s++; //printf("%d %d :: %lld\n",i,j,sum); ret += sum; } } return ret; } int main() { int num_nodes = NumberOfNodes(); int my_id = MyNodeId(); int n = GetFieldHeight(); int m = GetFieldWidth(); int begin_row = n * my_id / num_nodes; int end_row = n * (my_id + 1) / num_nodes; std::vector<int> my_verts(m); count_verts(my_verts, begin_row, end_row, m); std::vector<int> up(m); const int SHARDS = std::min(300, m); for (int k = 0; k < SHARDS; k++) { int begin_col = m * k / SHARDS; int end_col = m * (k+1) / SHARDS; if (my_id > 0) { Receive(my_id - 1); for (int j = begin_col; j < end_col; j++) up[j] = GetInt(my_id - 1); } for (int j = begin_col; j < end_col; j++) { if (my_verts[j] == end_row - begin_row) my_verts[j] += up[j]; } if (my_id < num_nodes - 1) { for (int j = begin_col; j < end_col; j++) PutInt(my_id + 1, my_verts[j]); Send(my_id + 1); } } long long sum = count(up, begin_row, end_row, m); if (my_id < num_nodes - 1) { PutLL(num_nodes - 1, sum); Send(num_nodes - 1); } else { for (int i = 0; i < num_nodes - 1; i++) { int v = Receive(-1); sum += GetLL(v); } printf("%lld\n", sum); } return 0; } |