Guest User

Untitled

a guest
Feb 19th, 2016
2,275
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.43 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i, n) for (int i = 0; i < int(n); i++)
  4. #define nfor(i, n) for (int i = int(n) - 1; i >= 0; i--)
  5. #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
  6. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  7. #define all(a) (a).begin(), (a).end()
  8. #define sz(a) int((a).size())
  9. #define pb(a) push_back(a)
  10. #define mp(x, y) make_pair((x), (y))
  11. #define x first
  12. #define y second
  13.  
  14. using namespace std;
  15.  
  16. typedef long long li;
  17. typedef long double ld;
  18. typedef pair<int, int> pt;
  19.  
  20. template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
  21. template<typename X> inline X sqr(const X& a) { return a * a; }
  22.  
  23. const int INF = int(1e9);
  24. const li INF64 = li(1e18);
  25. const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
  26.  
  27. const int N = 3030;
  28.  
  29. int n, m;
  30. char a[N][N];
  31.  
  32. inline bool read() {
  33.     if (!(cin >> n >> m)) return false;
  34.     assert(gets(a[0]));
  35.     forn(i, n) assert(gets(a[i]));
  36.     return true;
  37. }
  38.  
  39. inline void inc(int* t, int i, int v) {
  40.     for ( ; i < m; i |= i + 1) t[i] += v;
  41. }
  42. inline int sum(int* t, int i) {
  43.     int ans = 0;
  44.     for ( ; i >= 0; i = (i & (i + 1)) - 1)
  45.         ans += t[i];
  46.     return ans;
  47. }
  48. inline int sum(int* t, int i, int j) { return sum(t, j) - sum(t, i - 1); }
  49.  
  50. int zl[N][N], zld[N][N], zr[N][N];
  51. int t[2 * N][N];
  52. vector<pt> ev[N];
  53.  
  54. inline void solve() {
  55.     nfor(i, n)
  56.         forn(j, m)
  57.             if (a[i][j] == '.')
  58.                 zl[i][j] = zld[i][j] = 0;
  59.             else {
  60.                 zl[i][j] = zld[i][j] = 1;
  61.                 if (j > 0) zl[i][j] += zl[i][j - 1];
  62.                 if (j > 0 && i + 1 < n) zld[i][j] += zld[i + 1][j - 1];
  63.             }
  64.  
  65.     forn(i, n)
  66.         nfor(j, m)
  67.             if (a[i][j] == '.')
  68.                 zr[i][j] = 0;
  69.             else {
  70.                 zr[i][j] = 1;
  71.                 if (j + 1 < m) zr[i][j] += zr[i][j + 1];
  72.             }
  73.  
  74.     forn(j, m) ev[j].clear();
  75.     forn(i, n) forn(j, m) if (zr[i][j]) ev[j + zr[i][j] - 1].pb(pt(i, j));
  76.  
  77.     forn(i, n + m) forn(j, m) t[i][j] = 0;
  78.  
  79.     li ans = 0;
  80.     nfor(j, m) {
  81.         forn(i, sz(ev[j])) {
  82.             int x = ev[j][i].x;
  83.             int y = ev[j][i].y;
  84.             inc(t[x + y], y, +1);
  85.         }
  86.         forn(i, n) {
  87.             int c = min(zl[i][j], zld[i][j]);
  88.             if (!c) continue;
  89.             ans += sum(t[i + j], j - c + 1, j);
  90.         }
  91.     }
  92.     cout << ans << endl;
  93. }
  94.  
  95. int main() {
  96. #ifdef SU1
  97.     assert(freopen("input.txt", "rt", stdin));
  98.     //assert(freopen("output.txt", "wt", stdout));
  99. #endif
  100.    
  101.     cout << setprecision(10) << fixed;
  102.     cerr << setprecision(5) << fixed;
  103.  
  104.     while (read()) {
  105.         solve();
  106.         //break;
  107.     }
  108.    
  109.     return 0;
  110. }
Advertisement
Add Comment
Please, Sign In to add comment