oj.uz

Submission #857641

# Submission time Handle Problem Language Result Execution time Memory
857641 2023-10-06T14:59:55 Z serifefedartar Strah (COCI18_strah) C++17
66 / 110
 1000 ms 35896 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 = 2010;

vector<int> occ[2005];
int N, M;
int grid[MAXN][MAXN], emp[MAXN][MAXN];
int sg[4*MAXN], lazy[4*MAXN];
ll total = 0, ans = 0;
void push(int k, int a, int b) {
	if (lazy[k] != -1) {
		sg[k] = lazy[k];
		if (a != b) {
			lazy[2*k] = lazy[k];
			lazy[2*k+1] = lazy[k];
		}
		lazy[k] = -1;
	}
}

void update(int k, int a, int b, int q_l, int q_r, int new_val) {
	push(k, a, b);
	if (q_r < a || q_l > b)
		return ;
	if (q_l <= a && b <= q_r) {
		lazy[k] = new_val;
		push(k, a, b);
		return ;
	}
	update(2*k, a, (a+b)/2, q_l, q_r, new_val);
	update(2*k+1, (a+b)/2+1, b, q_l, q_r, new_val);
	sg[k] = max(sg[2*k], sg[2*k+1]);
}

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

int get(int k, int a, int b, int pos) {
	push(k, a, b);
	if (b < pos || a > pos)
		return 0;
	if (a == b)
		return sg[k];
	return get(2*k, a, (a+b)/2, pos) + get(2*k+1, (a+b)/2+1, b, pos);
}

int query(int k, int a, int b, int val) {
	push(k, a, b);
	if (a == b) {
		if (sg[k] >= val)
			return a;
		return N+1;
	}
	push(2*k, a, (a+b)/2);
	if (sg[2*k] < val)
		return query(2*k+1, (a+b)/2 + 1, b, val);
	return query(2*k, a, (a+b)/2, val);
}

void split(int pos) {
	int Q = get(1, 0, N, pos);
	int l = query(1, 0, N, Q);
	int r = query(1, 0, N, Q + 1) - 1;
	ans -= calc(r - l);
	ans += calc(pos - l - 1);
	ans += calc(r - pos);
	update(1, 0, N, pos, r, pos);
}

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

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

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

	for (int j = 1; j <= M; j++) {
		memset(sg, 0, sizeof(sg));
		memset(lazy, -1, sizeof(lazy));

		ans = calc(N);
		for (int q = 1; q <= 2000; q++)
			occ[q].clear();

		for (int i = 1; i <= N; i++) {
			if (emp[i][j] == 0)
				split(i);
			else
				occ[emp[i][j]].push_back(i);
		}

		for (ll q = 1; q <= 2000; q++) {
			total += ans * q;
			for (auto u : occ[q])
				split(u);
		}
	}
	cout << total << "\n";
}

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6236 KB Output is correct
2 Correct 31 ms 6236 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6236 KB Output is correct
2 Correct 29 ms 6232 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 6620 KB Output is correct
2 Correct 31 ms 6264 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 15440 KB Output is correct
2 Correct 908 ms 26876 KB Output is correct

Subtask #7
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 883 ms 23372 KB Output is correct
2 Execution timed out 1049 ms 31832 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 15788 KB Output is correct
2 Execution timed out 1032 ms 27732 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 25176 KB Output is correct
2 Execution timed out 1073 ms 32400 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1036 ms 35896 KB Time limit exceeded
2 Halted 0 ms 0 KB -