Submission #3414795

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;

void cmax(int &x, int y) {
  if (x < y) {
    x = y;
  }
}

void cmin(int &x, int y) {
  if (x > y) {
    x = y;
  }
}

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  int n;
  cin >> n;
  vector<string> board(n);
  for (int i = 0; i < n; ++i) {
    cin >> board[i];
  }
  long long answer = 0;

  function<void(vector<string>)> solve = [&](vector<string> board) {
    int n = board.size(), m = board[0].size();
    
    if (n < m) {
      vector<string> rotated(m, string(n, ' '));
      for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
          rotated[j][i] = board[i][j];
        }
      }
      swap(n, m);
      board = rotated;
    }
    
    if (m == 1) {
      int sum = 0;
      for (int i = 0; i < n; ++i) {
        if (board[i][0] == '#') {
          sum = 0;
        } else {
          answer += (board[i][0] - '0') * sum;
          sum += board[i][0] - '0';
        }
      }
      return;
    }

    vector<string> u = vector<string> (board.begin(), board.begin() + (n >> 1));
    vector<string> d = vector<string> (board.begin() + (n >> 1), board.end());
    solve(u);
    solve(d);
    u.push_back(d[0]);

    int nu = n >> 1, nd = n + 1 >> 1;
    vector<vector<int>> left(nd, vector<int> (m, inf));
    vector<vector<int>> right(nd, vector<int> (m, -inf));
    vector<int> top(m);
    vector<int> bottom(m);
    for (int i = 0; i < m; ++i) {
      if (d[0][i] != '#') {
        left[0][i] = right[0][i] = i;
      }
    }
    for (int i = 0; i < nd; ++i) {
      for (int j = 0; j < m; ++j) {
        if (d[i][j] != '#') {
          if (i) {
            cmin(left[i][j], left[i - 1][j]);
            cmax(right[i][j], right[i - 1][j]);
          }
          if (j) {
            cmin(left[i][j], left[i][j - 1]);
            cmax(right[i][j], right[i][j - 1]);
          }
        }
      }
    }

    {
      vector<vector<int>> temp(nd, vector<int> (m, -inf));
      for (int i = nd - 1; ~i; --i) {
        for (int j = m - 1; ~j; --j) {
          if (d[i][j] != '#') {
            temp[i][j] = i;
            if (i + 1 < nd) {
              cmax(temp[i][j], temp[i + 1][j]);
            }
            if (j + 1 < m) {
              cmax(temp[i][j], temp[i][j + 1]);
            }
          }
        }
      }
      for (int i = 0; i < m; ++i) {
        bottom[i] = temp[0][i];
      }
    }

    {
      vector<vector<int>> temp(nu + 1, vector<int> (m, inf));
      for (int i = 0; i <= nu; ++i) {
        for (int j = 0; j < m; ++j) {
          if (u[i][j] != '#') {
            temp[i][j] = i;
            if (i) {
              cmin(temp[i][j], temp[i - 1][j]);
            }
            if (j) {
              cmin(temp[i][j], temp[i][j - 1]);
            }
          }
        }
      }
      for (int i = 0; i < m; ++i) {
        top[i] = temp[nu][i];
      }
    }

    vector<vector<int>> mp(m, vector<int> (m, inf));
    for (int i = 0; i < nd; ++i) {
      for (int j = 0; j < m; ++j) {
        if (left[i][j] <= right[i][j]) {
          cmin(mp[left[i][j]][right[i][j]], i);
        }
      }
    }
    for (int l = 0; l < m; ++l) {
      for (int r = m - 1; ~r; --r) {
        if (l) {
          cmin(mp[l][r], mp[l - 1][r]);
        }
        if (r + 1 < m) {
          cmin(mp[l][r], mp[l][r + 1]);
        }
      }
    }

    auto meeting_point = [&](int a, int b) {
      int p = mp[a][b];
      return p <= min(bottom[a], bottom[b]) ? p : inf;
    };

    vector<int> sum1(nd);
    vector<vector<int>> sum2(nd, vector<int> (m));
    vector<vector<int>> sum3(nd, vector<int> (m));
    vector<vector<int>> sum4(m, vector<int> (m));

    for (int i = 0; i < nd; ++i) {
      if (i) {
        sum1[i] = sum1[i - 1];
        for (int j = 0; j < m; ++j) {
          sum2[i][j] = sum2[i - 1][j];
          sum3[i][j] = sum3[i - 1][j];
        }
      }
      for (int j = 0; j < m; ++j) {
        if (left[i][j] <= right[i][j]) {
          sum1[i] += d[i][j] - '0';
          if (left[i][j]) {
            sum2[i][left[i][j] - 1] += d[i][j] - '0';
          }
          if (right[i][j] + 1 < m) {
            sum3[i][right[i][j] + 1] += d[i][j] - '0';
          }
          if (left[i][j] && right[i][j] + 1 < m) {
            sum4[left[i][j] - 1][right[i][j] + 1] += d[i][j] - '0';
          }
        }
      }
    }
    for (int i = 0; i < nd; ++i) {
      for (int j = m - 1; j; --j) {
        sum2[i][j - 1] += sum2[i][j];
      }
      for (int j = 1; j < m; ++j) {
        sum3[i][j] += sum3[i][j - 1];
      }
    }
    for (int l = m - 1; ~l; --l) {
      for (int r = l; r < m; ++r) {
        if (l + 1 < m) {
          sum4[l][r] += sum4[l + 1][r];
        }
        if (r) {
          sum4[l][r] += sum4[l][r - 1];
        }
        if (l + 1 < m && r) {
          sum4[l][r] -= sum4[l + 1][r - 1];
        }
      }
    }

    auto both_reachable = [&](int a, int b, int l) {
      if (meeting_point(a, b) > l) {
        return 0;
      } else {
        return sum1[l] - sum2[l][a] - sum3[l][b] + sum4[a][b];
      }
    };

    vector<int> reachable(m);
    for (int i = 0; i < m; ++i) {
      reachable[i] = both_reachable(i, i, bottom[i]);
    }

    vector<vector<int>> event(nu);
    vector<bool> ban(m);
    for (int i = 0; i < m; ++i) {
      if (top[i] >= nu) {
        ban[i] = true;
      } else {
        event[top[i]].push_back(i);
      }
    }
    vector<int> l(m), r(m);
    for (int i = m - 1; ~i; --i) {
      if (d[0][i] == '#') {
        l[i] = inf;
        r[i] = -inf;
      } else {
        l[i] = i;
        r[i] = max(i, i + 1 < m ? r[i + 1] : -inf);
      }
    }
    for (int row = nu - 1; ~row; --row) {
      for (int i = m - 1; ~i; --i) {
        if (u[row][i] == '#') {
          l[i] = inf;
          r[i] = -inf;
        } else if (i + 1 < m) {
          cmin(l[i], l[i + 1]);
          cmax(r[i], r[i + 1]);
        }
      }
      vector<int> has(m);
      vector<int> st(m);
      int sum = 0, stl = 0, str = 0, myl = 0, myr = -1;
      
      auto insert = [&](int x) {
        if (!ban[x]) {
          if (stl < str) {
            sum -= has[st[str - 1]];
            has[st[str - 1]] -= both_reachable(st[str - 1], x, min(bottom[st[str - 1]], bottom[x]));
            sum += has[st[str - 1]];
            if (bottom[st[str - 1]] <= bottom[x]) {
              --str;
              while (stl < str) {
                sum -= has[st[str - 1]];
                has[st[str - 1]] -= both_reachable(st[str - 1], x, min(bottom[st[str - 1]], bottom[x])) - both_reachable(st[str - 1], x, min(bottom[st[str]], bottom[x]));
                sum += has[st[str - 1]];
                if (bottom[st[str - 1]] <= bottom[x]) {
                  --str;
                } else {
                  break;
                }
              }
            }
          }
          st[str++] = x;
          has[x] = reachable[x];
          sum += has[x];
        }
      };

      auto erase = [&](int x) {
        if (!ban[x]) {
          sum -= has[x];
          if (stl < str && st[stl] == x) {
            ++stl;
          }
        }
      };

      for (int i = 0; i < m; ++i) {
        if (l[i] <= r[i]) {
          while (myr < r[i]) {
            insert(++myr);
          }
          while (myl < l[i]) {
            erase(myl++);
          }
          answer += (u[row][i] - '0') * sum;
        }
      }
      for (auto p : event[row]) {
        ban[p] = true;
      }
    }
  };

  solve(board);
  cout << answer << endl;
  return 0;
}

Submission Info

Judge Result