Submission #306704

#	Time	Username	Problem	Language	Result	Execution time	Memory
306704		shivensinha4	Strah (COCI18_strah)	C++17	110 / 110	491 ms	16836 KiB

strah

#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;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11