Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define forn(i, n) for (int i = 0; i < int(n); i++)
- #define nfor(i, n) for (int i = int(n) - 1; i >= 0; i--)
- #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
- #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
- #define all(a) (a).begin(), (a).end()
- #define sz(a) int((a).size())
- #define pb(a) push_back(a)
- #define mp(x, y) make_pair((x), (y))
- #define x first
- #define y second
- using namespace std;
- typedef long long li;
- typedef long double ld;
- typedef pair<int, int> pt;
- template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
- template<typename X> inline X sqr(const X& a) { return a * a; }
- const int INF = int(1e9);
- const li INF64 = li(1e18);
- const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
- const int N = 3030;
- int n, m;
- char a[N][N];
- inline bool read() {
- if (!(cin >> n >> m)) return false;
- assert(gets(a[0]));
- forn(i, n) assert(gets(a[i]));
- return true;
- }
- inline void inc(int* t, int i, int v) {
- for ( ; i < m; i |= i + 1) t[i] += v;
- }
- inline int sum(int* t, int i) {
- int ans = 0;
- for ( ; i >= 0; i = (i & (i + 1)) - 1)
- ans += t[i];
- return ans;
- }
- inline int sum(int* t, int i, int j) { return sum(t, j) - sum(t, i - 1); }
- int zl[N][N], zld[N][N], zr[N][N];
- int t[2 * N][N];
- vector<pt> ev[N];
- inline void solve() {
- nfor(i, n)
- forn(j, m)
- if (a[i][j] == '.')
- zl[i][j] = zld[i][j] = 0;
- else {
- zl[i][j] = zld[i][j] = 1;
- if (j > 0) zl[i][j] += zl[i][j - 1];
- if (j > 0 && i + 1 < n) zld[i][j] += zld[i + 1][j - 1];
- }
- forn(i, n)
- nfor(j, m)
- if (a[i][j] == '.')
- zr[i][j] = 0;
- else {
- zr[i][j] = 1;
- if (j + 1 < m) zr[i][j] += zr[i][j + 1];
- }
- forn(j, m) ev[j].clear();
- forn(i, n) forn(j, m) if (zr[i][j]) ev[j + zr[i][j] - 1].pb(pt(i, j));
- forn(i, n + m) forn(j, m) t[i][j] = 0;
- li ans = 0;
- nfor(j, m) {
- forn(i, sz(ev[j])) {
- int x = ev[j][i].x;
- int y = ev[j][i].y;
- inc(t[x + y], y, +1);
- }
- forn(i, n) {
- int c = min(zl[i][j], zld[i][j]);
- if (!c) continue;
- ans += sum(t[i + j], j - c + 1, j);
- }
- }
- cout << ans << endl;
- }
- int main() {
- #ifdef SU1
- assert(freopen("input.txt", "rt", stdin));
- //assert(freopen("output.txt", "wt", stdout));
- #endif
- cout << setprecision(10) << fixed;
- cerr << setprecision(5) << fixed;
- while (read()) {
- solve();
- //break;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment