This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*
ID: varunra2
LANG: C++
TASK: strah
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifdef DEBUG
#include "lib/debug.h"
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define debug_arr(...) \
cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__)
#pragma GCC diagnostic ignored "-Wsign-compare"
//#pragma GCC diagnostic ignored "-Wunused-parameter"
//#pragma GCC diagnostic ignored "-Wunused-variable"
#else
#define debug(...) 42
#endif
#define EPS 1e-9
#define IN(A, B, C) assert(B <= A && A <= C)
#define INF (int)1e9
#define MEM(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define MP make_pair
#define PB push_back
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define x first
#define y second
const double PI = acos(-1.0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef map<int, int> MPII;
typedef multiset<int> MSETI;
typedef set<int> SETI;
typedef set<string> SETS;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef vector<string> VS;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define trav(a, x) for (auto& a : x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma GCC diagnostic ignored "-Wsign-compare"
// util functions
int n, m;
VVI grid;
VVI cnt;
int ret = 0;
void init() {
grid.resize(n);
trav(x, grid) x.resize(m);
}
int calc(int val) { return (val * (val + 1)) / 2; }
int calc(int l, int r) { return calc(r) - calc(l - 1); }
ll solve(VI& cur, int pos) {
int ret = 0;
int sum1 = 0; // sums of cur of all elements
int sum2 = 0; // sums of cur * i of all elements
stack<PII> st;
for (int i = 0; i < n; i++) {
PII val(cur[i], 1); // val, cnt
int ind = i;
while (!st.empty() and st.top().x >= val.x) {
sum1 -= calc(st.top().x) * st.top().y;
sum2 -= calc(st.top().x) * calc(ind - st.top().y + 1, ind);
ind -= st.top().y;
val.y += st.top().y;
st.pop();
}
st.push(val);
sum1 += val.y * calc(val.x);
sum2 += calc(ind + 1, i + 1) * calc(val.x);
int cur = (i + 2) * sum1 - sum2;
ret += cur;
}
return ret;
}
int32_t main() {
cin.sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
init();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char c;
cin >> c;
if (c == '.')
grid[i][j] = 1;
else
grid[i][j] = 0;
}
}
cnt = grid;
for (int i = 0; i < n; i++) {
for (int j = 1; j < m; j++) {
if (grid[i][j]) cnt[i][j] += cnt[i][j - 1];
}
}
for (int i = 0; i < m; i++) {
VI cur;
for (int j = 0; j < n; j++) {
cur.PB(cnt[j][i]);
}
ret += solve(cur, i);
}
// trav(x, cnt) debug(x);
cout << ret << '\n';
return 0;
}
# | 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... |