fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1005;
  4.  
  5. int n, m, R[N][N], U[N][N], D[N][N], ans[N][N];
  6. char mat[N][N];
  7. vector<int> A;
  8.  
  9. int main() {
  10.   ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  11.   cin >> n >> m;
  12.   for (int i = 1; i <= n; ++i) {
  13.     for (int j = 1; j <= m; ++j) {
  14.       cin >> mat[i][j];
  15.     }
  16.     for (int j = m; j >= 1; --j) {
  17.       if (mat[i][j] == '*') {
  18.         R[i][j] = 0;
  19.       } else {
  20.         R[i][j] = R[i][j + 1] + 1;
  21.       }
  22.     }
  23.   }
  24.  
  25.   for (int j = 1; j <= m; ++j) {
  26.     A.clear();
  27.     for (int i = 1; i <= n; ++i) {
  28.       while (!A.empty() && R[i][j] < R[A.back()][j]) A.pop_back();
  29.       U[i][j] = A.empty() ? 1 : (A.back() + 1);
  30.       A.push_back(i);
  31.     }
  32.     A.clear();
  33.     for (int i = n; i >= 1; --i) {
  34.       while (!A.empty() && R[i][j] <= R[A.back()][j]) A.pop_back();
  35.       D[i][j] = A.empty() ? n : (A.back() - 1);
  36.       A.push_back(i);
  37.     }
  38.   }
  39.  
  40.   for (int i = 1; i <= n; ++i) {
  41.     for (int j = 1; j <= m; ++j) {
  42.       // increase ans[i - Ui + 1] -> ans[Di - Ui + 1]
  43.       //          ans[i - (Ui + 1) + 1] -> ans[Di - (Ui + 1) + 1]
  44.       //          ...
  45.       //          ans[i - i + 1] -> ans[Di - i + 1]
  46.       ++ans[1][R[i][j]];
  47.       --ans[i - U[i][j] + 2][R[i][j]];
  48.       --ans[D[i][j] - i + 2][R[i][j]];
  49.       ++ans[D[i][j] - U[i][j] + 3][R[i][j]];
  50.     }
  51.   }
  52.   for (int j = 1; j <= m; ++j) {
  53.     for (int i = 1; i <= n; ++i) {
  54.       ans[i][j] += ans[i - 1][j];
  55.     }
  56.     for (int i = 1; i <= n; ++i) {
  57.       ans[i][j] += ans[i - 1][j];
  58.     }
  59.   }
  60.   for (int i = n; i >= 1; --i) {
  61.     for (int j = m; j >= 2; --j) {
  62.       ans[i][j - 1] += ans[i][j];
  63.     }
  64.   }
  65.   for (int i = 1; i <= n; ++i) {
  66.     for (int j = 1; j <= m; ++j) {
  67.       cout << ans[i][j] << " \n"[j == m];
  68.     }
  69.   }
  70.   return 0;
  71. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tDN3XX
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!