#include <bits/stdc++.h>
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
//#define endl '\n'
ll f(ll x) {
return (x * (x+1)) / 2;
}
int main() {
#ifdef shiven
freopen("test.in", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m; cin >> n >> m;
vector<vector<bool>> mat(n, vector<bool>(m));
for_(i, 0, n) for_(j, 0, m) {
char c; cin >> c;
mat[i][j] = c == '.';
}
vector<vi> up(n, vi(m));
for_(i, 0, n) for_(j, 0, m) {
up[i][j] = mat[i][j];
if (i > 0 and up[i][j]) up[i][j] += up[i-1][j];
}
ll ans = 0;
for_(i, 0, n) {
stack<pair<ll, ll>> st; // height, node
vector<vector<ll>> temp(m); // width, ans, f(h)*w sum
for (int j = m-1; j >= 0; j--) {
if (!mat[i][j]) {
stack<pair<ll, ll>> s;
swap(s, st);
continue;
}
ll ca = 0, cs = 0, w = 1;
while (st.size() and st.top().first > up[i][j]) {
w += temp[st.top().second][0]; st.pop();
}
if (st.size()) {
ll p = st.top().second;
cs += temp[p][2]; ca += temp[p][1] + temp[p][2] * (p-j);
}
ca += f(up[i][j]) * f(w);
cs += f(up[i][j]) * w;
ans += ca;
temp[j] = {w, ca, cs};
st.push({up[i][j], j});
}
}
cout << ans << endl;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
768 KB |
Output is correct |
2 |
Correct |
13 ms |
768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
768 KB |
Output is correct |
2 |
Correct |
10 ms |
768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
768 KB |
Output is correct |
2 |
Correct |
10 ms |
768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
125 ms |
4856 KB |
Output is correct |
2 |
Correct |
236 ms |
10360 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
292 ms |
10616 KB |
Output is correct |
2 |
Correct |
362 ms |
15464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
143 ms |
6776 KB |
Output is correct |
2 |
Correct |
263 ms |
11128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
1656 KB |
Output is correct |
2 |
Correct |
289 ms |
12408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
376 ms |
16760 KB |
Output is correct |
2 |
Correct |
491 ms |
16836 KB |
Output is correct |