fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main() {
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.     int n, m;
  9.     if (!(cin >> n >> m)) return 0;
  10.     vector<string> a(n);
  11.     for (int i = 0; i < n; ++i) cin >> a[i];
  12.  
  13.     // U[i][j]: số ô '.' liên tiếp lên trên (tính từ hàng 1..n, cột 1..m)
  14.     vector<vector<int>> U(n, vector<int>(m, 0));
  15.     for (int j = 0; j < m; ++j) {
  16.         for (int i = 0; i < n; ++i) {
  17.             if (a[i][j] == '.') {
  18.                 U[i][j] = (i == 0 ? 1 : U[i-1][j] + 1);
  19.             } else U[i][j] = 0;
  20.         }
  21.     }
  22.  
  23.     // diff arrays per Hvalue (Hvalue from 0..n). We'll use indices 1..m for widths.
  24.     // For each Hval we keep coefDiff and constDiff (for linear function alpha*w + beta)
  25.     int Hmax = n;
  26.     vector<vector<ll>> coefDiff(Hmax+1, vector<ll>(m+3, 0));
  27.     vector<vector<ll>> constDiff(Hmax+1, vector<ll>(m+3, 0));
  28.  
  29.     // Process each row as bottom
  30.     for (int i = 0; i < n; ++i) {
  31.         vector<int> H(m);
  32.         for (int j = 0; j < m; ++j) H[j] = U[i][j];
  33.  
  34.         // prev less (strict)
  35.         vector<int> L(m);
  36.         {
  37.             vector<int> st;
  38.             for (int j = 0; j < m; ++j) {
  39.                 while (!st.empty() && H[st.back()] >= H[j]) st.pop_back();
  40.                 L[j] = st.empty() ? -1 : st.back();
  41.                 st.push_back(j);
  42.             }
  43.         }
  44.         // next less or equal
  45.         vector<int> R(m);
  46.         {
  47.             vector<int> st;
  48.             for (int j = m-1; j >= 0; --j) {
  49.                 while (!st.empty() && H[st.back()] > H[j]) st.pop_back();
  50.                 R[j] = st.empty() ? m : st.back();
  51.                 st.push_back(j);
  52.             }
  53.         }
  54.  
  55.         for (int j = 0; j < m; ++j) {
  56.             int hval = H[j];
  57.             if (hval <= 0) continue; // không đóng góp nếu U=0
  58.  
  59.             int leftIndex = L[j];   // L
  60.             int rightIndex = R[j];  // R
  61.             int S = rightIndex - leftIndex - 1; // độ dài đoạn mà j là minimum
  62.             // A = số ô có thể lấy bên trái (a từ 0..A)
  63.             int A = j - leftIndex - 1;
  64.             // B = số ô có thể lấy bên phải (b từ 0..B)
  65.             int B = rightIndex - j - 1;
  66.  
  67.             int small = min(A, B);
  68.             int large = max(A, B);
  69.  
  70.             // Ranges in w (1-based widths)
  71.             // Range1: w in [1 .. small+1], value = w  (linear with coef=1, const=0)
  72.             int l1 = 1, r1 = small + 1;
  73.             if (l1 <= r1) {
  74.                 coefDiff[hval][l1] += 1;
  75.                 coefDiff[hval][r1 + 1] -= 1;
  76.                 // const 0 -> no change
  77.             }
  78.             // Range2: w in [small+2 .. large+1], value = small+1 (constant)
  79.             int l2 = small + 2, r2 = large + 1;
  80.             if (l2 <= r2) {
  81.                 constDiff[hval][l2] += (small + 1);
  82.                 constDiff[hval][r2 + 1] -= (small + 1);
  83.             }
  84.             // Range3: w in [large+2 .. S], value = S - w + 1 = (-1)*w + (S+1)
  85.             int l3 = large + 2, r3 = S;
  86.             if (l3 <= r3) {
  87.                 coefDiff[hval][l3] += -1;
  88.                 coefDiff[hval][r3 + 1] -= -1;
  89.                 constDiff[hval][l3] += (S + 1);
  90.                 constDiff[hval][r3 + 1] -= (S + 1);
  91.             }
  92.         }
  93.     }
  94.  
  95.     // Now build Smax[Hval][w] by prefixing diffs, then suffix by H to get ans[h][w]
  96.     vector<vector<ll>> ans(n+1, vector<ll>(m+1, 0)); // 1-based h and w
  97.     vector<ll> sumW(m+1, 0); // suffix accumulator for widths
  98.  
  99.     // iterate Hval from high to low, produce its Smax row and add to running sumW to get ans[Hval][*]
  100.     for (int Hval = Hmax; Hval >= 1; --Hval) {
  101.         ll prefCoef = 0, prefConst = 0;
  102.         for (int w = 1; w <= m; ++w) {
  103.             prefCoef += coefDiff[Hval][w];
  104.             prefConst += constDiff[Hval][w];
  105.             ll S = prefCoef * (ll)w + prefConst; // sum of F_j(w) for j with H[j] == Hval
  106.             sumW[w] += S;                        // add to suffix (H' >= current Hval)
  107.             ans[Hval][w] = sumW[w];
  108.         }
  109.     }
  110.  
  111.     // For h that have no direct Hval (e.g., 0) ans will be zero; output h=1..n
  112.     // print as sample: each row h (1..n) print m numbers (w=1..m) with spaces and trailing space
  113.     for (int h = 1; h <= n; ++h) {
  114.         for (int w = 1; w <= m; ++w) {
  115.             cout << ans[h][w];
  116.             if (w < m) cout << ' ';
  117.             else cout << ' ';
  118.         }
  119.         cout << '\n';
  120.     }
  121.     return 0;
  122. }
  123.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/irgsTg
language:
C++14 (gcc 8.3)
created:
13 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!