Advertisement
Dang_Quan_10_Tin

VILLA

Sep 9th, 2023
1,196
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.05 KB | None | 0 0
  1. #define task "VILLA"
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5. using ll = long long;
  6.  
  7. constexpr int N = 2e3 + 5;
  8. int m, n;
  9.  
  10. string s[N];
  11. int a[N][N];
  12. int16_t last[N][N];
  13. int16_t start[N][N];
  14. ll x[N][N], y[N][N];
  15.  
  16. void Read()
  17. {
  18.     cin >> m >> n;
  19.  
  20.     for (int i = 1; i <= m; ++i)
  21.     {
  22.         cin >> s[i];
  23.         s[i] = " " + s[i];
  24.         for (int j = 1; j <= n; ++j)
  25.             a[i][j] = (s[i][j] == '#') + a[i][j - 1];
  26.     }
  27. }
  28.  
  29. #define Get(x, y, z) (a[x][z] - a[x][y - 1])
  30.  
  31. void Solve()
  32. {
  33.     ll ans = m * n;
  34.  
  35.     for (int i = 1; i <= m; ++i)
  36.         ans -= a[i][n];
  37.  
  38.     ans = ans * (ans + 1) / 2;
  39.  
  40.     for (int i = 1; i <= m; ++i)
  41.         for (int j = 1; j <= n; ++j)
  42.         {
  43.             start[i][j] = -1;
  44.             if (s[i][j] == '#')
  45.                 last[i][j] = j;
  46.             else
  47.                 last[i][j] = last[i][j - 1];
  48.  
  49.             if (s[i][j] == '#')
  50.             {
  51.                 start[i][j] = j;
  52.                 if (s[i][j - 1] == '#')
  53.                     start[i][j] = start[i][j - 1];
  54.             }
  55.             if (s[i][j] != '#')
  56.             {
  57.                 int l = last[i][j],
  58.                     r = j;
  59.  
  60.                 x[i][l] = x[i - 1][last[i - 1][l]] - l + a[i][l];
  61.                 y[i][r] = y[i - 1][s[i - 1][r] == '#' ? (start[i - 1][r] - 1) : r] + r - a[i][r];
  62.  
  63.                 ans -= x[i][l] + y[i][r];
  64.  
  65.                 /*for (int t = i; t && l < r; --t)
  66.                 {
  67.                     ans -= r - l - Get(t, l + 1, r);
  68.  
  69.                     if (t != 1)
  70.                     {
  71.                         if (s[t - 1][r] == '#')
  72.                             r = start[t - 1][r] - 1;
  73.                         l = last[t - 1][l];
  74.                     }
  75.                 }*/
  76.             }
  77.         }
  78.  
  79.     cout << ans << endl;
  80. }
  81.  
  82. int32_t main()
  83. {
  84.     ios::sync_with_stdio(0);
  85.     cin.tie(0);
  86.     cout.tie(0);
  87.  
  88.     if (fopen(task ".INP", "r"))
  89.     {
  90.         freopen(task ".INP", "r", stdin);
  91.         freopen(task ".OUT", "w", stdout);
  92.     }
  93.  
  94.     Read();
  95.     Solve();
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement