This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <stack>
#include <queue>
#include <deque>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef pair <int, int> pii;
//#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
// order_of_key (k) : Number of items strictly smaller than k .
// find_by_order(k) : K-th element in a set (counting from zero).
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define pb push_back
#define ppb pop_back
#define mkp make_pair
#define F first
#define S second
#define show(a) cerr << #a <<" -> "<< a <<"\n"
#define fo(a, b, c, d) for(int (a) = (b); (a) <= (c); (a) += (d))
#define foo(a, b, c ,d) for(int (a) = (b); (a) >= (c); (a) -= (d))
//#define int ll
const int N = 2e5 + 5;
const int INF = 1e9 + 5;
int n, m, l[N], r[N];
ll ans, h[N];
ll sum(ll x) {
return (x * (x + 1)) / 2;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
string str;
cin >> str;
str = "#" + str;
for(int j = 1; j <= m; ++j) {
if(str[j] == '.') ++h[j];
else h[j] = 0;
// cout << h[j] <<' ';
}
//cout << '\n';
vector <int> st;
for(int j = 1; j <= m; ++j) {
while(sz(st) && h[st.back()] >= h[j])
st.ppb();
if(!sz(st)) l[j] = 0;
else l[j] = st.back();
st.pb(j);
}
st.clear();
for(int j = m; j >= 1; --j) {
while(sz(st) && h[st.back()] > h[j])
st.ppb();
if(!sz(st)) r[j] = m + 1;
else r[j] = st.back();
st.pb(j);
}
for(int j = 1; j <= m; ++j) {
//cout << l[j] + 1 << r[j] - 1 <<' ';
ll cntL = j - l[j];
ll cntR = r[j] - j;
ans += sum(h[j]) * (cntR * sum(cntL) + cntL * sum(cntR) - cntL * cntR);
}
//cout << '\n';
}
cout << ans;
return 0;
}
/*
If you only do what you can do,
You will never be more than you are now!
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |