oj.uz

Submission #306706

# Submission time Handle Problem Language Result Execution time Memory
306706 2020-09-26T07:40:16 Z shivensinha4 Strah (COCI18_strah) C++17
110 / 110
 498 ms 16888 KB 
#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, vector<ll>(3)); // 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;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 288 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 768 KB Output is correct
2 Correct 10 ms 768 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 768 KB Output is correct
2 Correct 10 ms 768 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 768 KB Output is correct
2 Correct 10 ms 768 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 4856 KB Output is correct
2 Correct 256 ms 10360 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 10616 KB Output is correct
2 Correct 387 ms 15480 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 6776 KB Output is correct
2 Correct 260 ms 11256 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1536 KB Output is correct
2 Correct 280 ms 12408 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 16888 KB Output is correct
2 Correct 498 ms 16888 KB Output is correct