#include "dzialka.h" #include "message.h" #include <bits/stdc++.h> using namespace std; const int limit = 16000; const int N = 75001; int k[N]; int f[N]; pair<int, int> s[N]; typedef long long ll; int main() { int n = GetFieldHeight(), m = GetFieldWidth(); int id = MyNodeId(), nodes = NumberOfNodes(); if(n < nodes) { if(id >= n) return 0; nodes = min(n, nodes); } int begin = n / nodes * id, end = n / nodes * (id + 1); assert(end - begin <= 850); int w = end - begin; if(id == nodes - 1) end = n; for(int i = begin; i < end; i++) { for(int j = 1; j <= m; j++) { if(IsUsableCell(i, j-1)) k[j]++; else k[j] = 0; } } if(id > 0) { Receive(id - 1); int got = 0; for(int i = 1; i <= m; i++) { f[i] = GetInt(id - 1); if(++got == limit) { got = 0; if(i < m) Receive(id - 1); } if(k[i] == end - begin) k[i] += f[i]; } } if(id + 1 < nodes) { int put = 0; for(int i = 1; i <= m; i++) { PutInt(id + 1, k[i]); if(++put == limit) { Send(id + 1); put = 0; } } if(put) Send(id + 1); } ll ans = 0; for(int i = begin; i < end; i++) { auto *back = s; uint sum = 0; for(int j = 1; j <= m; j++) { if(IsUsableCell(i, j - 1)) f[j]++; else f[j] = 0; while(back->first > f[j]) { auto b = *back; back--; sum -= (uint)b.first * uint(b.second - back->second); } sum += (uint)f[j] * uint(j - back->second); ans += sum; *(++back) = { f[j], j }; } } if(id > 0) { Receive(id - 1); ans += GetLL(id - 1); } if(id + 1 < nodes) { PutLL(id + 1, ans); Send(id + 1); } else printf("%lld\n", ans); }
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 | #include "dzialka.h" #include "message.h" #include <bits/stdc++.h> using namespace std; const int limit = 16000; const int N = 75001; int k[N]; int f[N]; pair<int, int> s[N]; typedef long long ll; int main() { int n = GetFieldHeight(), m = GetFieldWidth(); int id = MyNodeId(), nodes = NumberOfNodes(); if(n < nodes) { if(id >= n) return 0; nodes = min(n, nodes); } int begin = n / nodes * id, end = n / nodes * (id + 1); assert(end - begin <= 850); int w = end - begin; if(id == nodes - 1) end = n; for(int i = begin; i < end; i++) { for(int j = 1; j <= m; j++) { if(IsUsableCell(i, j-1)) k[j]++; else k[j] = 0; } } if(id > 0) { Receive(id - 1); int got = 0; for(int i = 1; i <= m; i++) { f[i] = GetInt(id - 1); if(++got == limit) { got = 0; if(i < m) Receive(id - 1); } if(k[i] == end - begin) k[i] += f[i]; } } if(id + 1 < nodes) { int put = 0; for(int i = 1; i <= m; i++) { PutInt(id + 1, k[i]); if(++put == limit) { Send(id + 1); put = 0; } } if(put) Send(id + 1); } ll ans = 0; for(int i = begin; i < end; i++) { auto *back = s; uint sum = 0; for(int j = 1; j <= m; j++) { if(IsUsableCell(i, j - 1)) f[j]++; else f[j] = 0; while(back->first > f[j]) { auto b = *back; back--; sum -= (uint)b.first * uint(b.second - back->second); } sum += (uint)f[j] * uint(j - back->second); ans += sum; *(++back) = { f[j], j }; } } if(id > 0) { Receive(id - 1); ans += GetLL(id - 1); } if(id + 1 < nodes) { PutLL(id + 1, ans); Send(id + 1); } else printf("%lld\n", ans); } |