oj.uz

Submission #636513

# Submission time Handle Problem Language Result Execution time Memory
636513 2022-08-29T12:29:31 Z vovamr Strah (COCI18_strah) C++17
110 / 110
 172 ms 8248 KB 
#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.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 464 KB Output is correct
2 Correct 5 ms 468 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 2384 KB Output is correct
2 Correct 106 ms 5048 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 5188 KB Output is correct
2 Correct 151 ms 7576 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 3404 KB Output is correct
2 Correct 109 ms 5460 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 912 KB Output is correct
2 Correct 104 ms 6168 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 8244 KB Output is correct
2 Correct 172 ms 8248 KB Output is correct