oj.uz

Submission #306701

# Submission time Handle Problem Language Result Execution time Memory
306701 2020-09-26T07:37:59 Z shivensinha4 Strah (COCI18_strah) C++17
110 / 110
 377 ms 20728 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];
	}
	
	//for_(i, 0, n) {
		//for (int j: up[i]) cout << j << " ";
		//cout << endl;
	//}
	
	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]) {
				while (st.size()) st.pop();
				continue;
			}
			
			ll ca = 0, cs = 0, w = 1;
			
			while (st.size() and st.top().first > up[i][j]) {
				//pair<ll, ll> p = st.top(); 
				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 1 ms 384 KB Output is correct
2 Correct 1 ms 384 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 1 ms 384 KB Output is correct

Subtask #3
11.0 / 11.0

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

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 896 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 111 ms 5752 KB Output is correct
2 Correct 234 ms 12536 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 13048 KB Output is correct
2 Correct 351 ms 19064 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 8312 KB Output is correct
2 Correct 248 ms 13688 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1792 KB Output is correct
2 Correct 279 ms 15480 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 20728 KB Output is correct
2 Correct 376 ms 20728 KB Output is correct