#include "dzialka.h" #include "message.h" #include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int, int> PII; const ll mod = 1000000007; ll powmod(ll a, ll b) {ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) {if (b & 1)res = res * a % mod; a = a * a % mod;} return res;} ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;} // head const int N = 120, M = 75100; int n, m, T, Z, b, b2, l1[N], r1[N], plen[M], prer[M], l2[N], r2[N]; int stk[M], top, pl[M], pr[M], vl[M], vr[M]; ll ret; void gao() { int top = 0; rep(i, 0, m) { pl[i] = pr[i] = -1; int k = top; while (k > 0 && prer[stk[k - 1]] > prer[i]) --k; if (k) pr[stk[k - 1]] = i; if (k < top) pl[i] = stk[k]; stk[k++] = i; top = k; } rep(i, 0, m) if (pl[i] == -1) vl[i] = i; else vl[i] = vl[pl[i]]; per(i, 0, m) if (pr[i] == -1) vr[i] = i; else vr[i] = vr[pr[i]]; rep(i, 0, m) ret += (ll)(i - vl[i] + 1) * (vr[i] - i + 1) * prer[i]; } int main() { n = GetFieldHeight(); m = GetFieldWidth(); T = NumberOfNodes(); Z = MyNodeId(); b = (n + T - 1) / T; b2 = (m + T - 1) / T; rep(i, 0, T) l1[i] = min(i * b, n), r1[i] = min((i + 1) * b, n); rep(i, 0, T) l2[i] = min(i * b2, m), r2[i] = min((i + 1) * b2, m); rep(j, l2[Z], r2[Z]) { int len = 0; rep(i, 0, n) { plen[i] = len; if (IsUsableCell(i, j)) len++; else len = 0; } plen[n] = len; for (int i = 0; i < T; i++) PutInt(i, plen[l1[i]]); } rep(i, 0, T) Send(i); rep(i, 0, T) { Receive(i); rep(j, l2[i], r2[i]) prer[j] = GetInt(i); } for (int i = l1[Z]; i < r1[Z]; i++) { rep(j, 0, m) if (IsUsableCell(i, j)) prer[j]++; else prer[j] = 0; gao(); } PutLL(0, ret); Send(0); if (Z == 0) { ll ans = 0; rep(i, 0, T) { Receive(i); ans += GetLL(i); } 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 | #include "dzialka.h" #include "message.h" #include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int, int> PII; const ll mod = 1000000007; ll powmod(ll a, ll b) {ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) {if (b & 1)res = res * a % mod; a = a * a % mod;} return res;} ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;} // head const int N = 120, M = 75100; int n, m, T, Z, b, b2, l1[N], r1[N], plen[M], prer[M], l2[N], r2[N]; int stk[M], top, pl[M], pr[M], vl[M], vr[M]; ll ret; void gao() { int top = 0; rep(i, 0, m) { pl[i] = pr[i] = -1; int k = top; while (k > 0 && prer[stk[k - 1]] > prer[i]) --k; if (k) pr[stk[k - 1]] = i; if (k < top) pl[i] = stk[k]; stk[k++] = i; top = k; } rep(i, 0, m) if (pl[i] == -1) vl[i] = i; else vl[i] = vl[pl[i]]; per(i, 0, m) if (pr[i] == -1) vr[i] = i; else vr[i] = vr[pr[i]]; rep(i, 0, m) ret += (ll)(i - vl[i] + 1) * (vr[i] - i + 1) * prer[i]; } int main() { n = GetFieldHeight(); m = GetFieldWidth(); T = NumberOfNodes(); Z = MyNodeId(); b = (n + T - 1) / T; b2 = (m + T - 1) / T; rep(i, 0, T) l1[i] = min(i * b, n), r1[i] = min((i + 1) * b, n); rep(i, 0, T) l2[i] = min(i * b2, m), r2[i] = min((i + 1) * b2, m); rep(j, l2[Z], r2[Z]) { int len = 0; rep(i, 0, n) { plen[i] = len; if (IsUsableCell(i, j)) len++; else len = 0; } plen[n] = len; for (int i = 0; i < T; i++) PutInt(i, plen[l1[i]]); } rep(i, 0, T) Send(i); rep(i, 0, T) { Receive(i); rep(j, l2[i], r2[i]) prer[j] = GetInt(i); } for (int i = l1[Z]; i < r1[Z]; i++) { rep(j, 0, m) if (IsUsableCell(i, j)) prer[j]++; else prer[j] = 0; gao(); } PutLL(0, ret); Send(0); if (Z == 0) { ll ans = 0; rep(i, 0, T) { Receive(i); ans += GetLL(i); } printf("%lld\n", ans); } } |