Submission #636513

#	Time	Username	Problem	Language	Result	Execution time	Memory
636513		vovamr	Strah (COCI18_strah)	C++17	110 / 110	172 ms	8248 KiB

strah

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

inline void solve() {
	int n, m;
	cin >> n >> m;
	ve<ve<char>> a(n,ve<char>(m));
	for (auto &i : a) for (auto &j : i) cin >> j;

	ll ans = 0;

	ve<int> stk, cnt(m), l(m), r(m);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (a[i][j] == '.') ++cnt[j];
			else cnt[j] = 0;
		}

		stk = {0}; l[0] = -1;
		for (int i = 1; i < m; ++i) {
			while (sz(stk) && cnt[stk.back()] > cnt[i]) stk.pop_back();
			l[i] = sz(stk) ? stk.back() : -1;
			stk.pb(i);
		}
		stk = {m - 1}; r[m - 1] = m;
		for (int i = m - 2; ~i; --i) {
			while (sz(stk) && cnt[stk.back()] >= cnt[i]) stk.pop_back();
			r[i] = sz(stk) ? stk.back() : m;
			stk.pb(i);
		}

		for (int i = 0; i < m; ++i) {
			int len_l = i - l[i];
			int len_r = r[i] - i;

			ll H = cnt[i] * 1ll * (cnt[i] + 1) / 2ll;
			ll sa = len_l * 1ll * (len_l + 1) / 2ll;
			ll sb = len_r * 1ll * (len_r - 1) / 2ll;
			ans += H * (sa * 1ll * len_r + sb * len_l);
		}
	}

	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

• 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