fork download 
  1.  
  2. #include <bits/stdc++.h>
  3.  
  4. #define el '\n'
  5. #define fi first
  6. #define sec second
  7. #define pb push_back
  8. #define int long long
  9. #define pii pair<int,int>
  10. #define sz(v) (int)(v).size()
  11. #define all(v) (v).begin(),(v).end()
  12. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  13. #define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)
  14.  
  15. using namespace std;
  16.  
  17. const int INF = (int)1e18 + 462010;
  18. const int MAX_N = 2000;
  19.  
  20. int d1[MAX_N + 5][MAX_N + 5], d2[MAX_N + 5][MAX_N + 5], ans[MAX_N + 5][MAX_N + 5];
  21. int h[MAX_N + 5], L[MAX_N + 5], R[MAX_N + 5];
  22. bool a[MAX_N + 5][MAX_N + 5];
  23. int n, m;
  24.  
  25. void Input(){
  26.     cin >> n >> m;
  27.     FOR(i, 1, n){
  28.         string s;
  29.         cin >> s;
  30.         FOR(j, 1, m) a[i][j] = (s[j - 1] == '#');
  31.     }
  32. }
  33.  
  34. void process(int i){
  35.     FOR(j, 1, m)
  36.         h[j] = (!a[i][j] ? h[j] + 1 : 0LL);
  37.  
  38.     stack<int> st;
  39.     FOR(j, 1, m){
  40.         while(sz(st) && h[st.top()] >= h[j]) st.pop();
  41.  
  42.         L[j] = j - (sz(st) ? st.top() : 0);
  43.         st.push(j);
  44.     }
  45.  
  46.     while(sz(st)) st.pop();
  47.  
  48.     REP(j, m, 1){
  49.         while(sz(st) && h[st.top()] > h[j]) st.pop();
  50.  
  51.         R[j] = (sz(st) ? st.top() : m + 1) - j;
  52.         st.push(j);
  53.     }
  54.  
  55.     FOR(j, 1, m){
  56.         if(!h[j]) continue;
  57.  
  58.         int x = min(L[j], R[j]), y = max(L[j], R[j]);
  59.         int z = L[j] + R[j] - 1;
  60.  
  61.         d1[h[j]][1]++;
  62.         d1[h[j]][x + 1]--;
  63.  
  64.         d1[h[j]][y + 1]--;
  65.         d1[h[j]][z + 1]++;
  66.  
  67.         d2[h[j]][x + 1] += x;
  68.         d2[h[j]][y + 1] -= x;
  69.  
  70.         d2[h[j]][y + 1] += L[j] + R[j];
  71.         d2[h[j]][z + 1] -= L[j] + R[j];
  72.     }
  73. }
  74.  
  75. void Solve(){
  76.     FOR(i, 1, n) process(i);
  77.  
  78.     FOR(i, 1, n) FOR(j, 1, m){
  79.         d1[i][j] += d1[i][j - 1];
  80.         d2[i][j] += d2[i][j - 1];
  81.     }
  82.  
  83.     REP(i, n, 1) FOR(j, 1, m){
  84.         ans[i][j] = ans[i + 1][j];
  85.         ans[i][j] += d1[i][j] * j + d2[i][j];
  86.     }
  87.  
  88.     FOR(i, 1, n){
  89.         FOR(j, 1, m) cout << ans[i][j] << " ";
  90.         cout << el;
  91.     }
  92. }
  93.  
  94. signed main(){
  95.     ios_base::sync_with_stdio(0);
  96.     cin.tie(0);
  97.  
  98.     Input();
  99.     Solve();
  100.  
  101.     return 0;
  102. }
  103.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/YDWpAj
language:
C++ (gcc 8.3)
created:
1 day 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!