oj.uz

Submission #857713

# Submission time Handle Problem Language Result Execution time Memory
857713 2023-10-06T16:19:26 Z serifefedartar Strah (COCI18_strah) C++17
110 / 110
 896 ms 25768 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 18; 
const ll INF = 1e15;
const ll MAXN = 2005;

vector<int> occ[MAXN];
int N, M;
int emp[MAXN][MAXN];
ll total = 0, ans = 0;
set<pair<ll,ll>> st;

ll calc(ll x) {
	return (x * x * x + 3 * x * x + 2 * x) / 6;
}

void split(int pos) {
	pair<ll,ll> Q = *(prev(st.upper_bound(make_pair(pos, 1e8))));
	ans += calc(pos - Q.f) + calc(Q.f + Q.s - 1 - pos) - calc(Q.s);
	st.erase(Q);
	if (pos - Q.f > 0)
		st.insert({Q.f, pos - Q.f});
	if (Q.f + Q.s - 1 - pos > 0)
		st.insert({pos + 1, Q.f + Q.s - 1 - pos});
}

string s;
int main() {
	fast
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		cin >> s;
		for (int j = M; j >= 1; j--) {
			if (s[j-1] == '.')
				emp[i][j] = emp[i][j+1] + 1;
		}
	}

	for (int j = 1; j <= M; j++) {
		st.clear();
		st.insert({1, N});
		ans = calc(N);
		for (int i = 1; i <= N; i++)
			occ[emp[i][j]].push_back(i);

		for (ll q = 0; q <= 2000; q++) {
			total += ans * q;
			while (occ[q].size()) {
				split(occ[q].back());
				occ[q].pop_back();
			}
		}
	}
	cout << total << "\n";
}

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2084 KB Output is correct
2 Correct 19 ms 1884 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2096 KB Output is correct
2 Correct 18 ms 1880 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2652 KB Output is correct
2 Correct 18 ms 2092 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 7108 KB Output is correct
2 Correct 562 ms 12420 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 10960 KB Output is correct
2 Correct 896 ms 15744 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 7484 KB Output is correct
2 Correct 612 ms 13172 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 8796 KB Output is correct
2 Correct 701 ms 17872 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 819 ms 25768 KB Output is correct
2 Correct 891 ms 20160 KB Output is correct