Submission #524318

#	Time	Username	Problem	Language	Result	Execution time	Memory
524318		boykut	Bomb (IZhO17_bomb)	C++14	11 / 100	1101 ms	131076 KiB

bomb

#include <bits/stdc++.h>

using namespace std;

const int N = 2555;
int arr[N][N], brr[N][N];
int pref[N][N];
int t[N][N* 4], lazy[N][4 * N];

void push(int X, int v, int vl, int vr) {
	if (vl == vr || lazy[X][v] == -1) return;
	lazy[X][v << 1] = lazy[X][v];
	lazy[X][v << 1 | 1] = lazy[X][v];
	int vm = vl + vr >> 1;
	t[X][v << 1] = lazy[X][v] * (vm - vl + 1);
	t[X][v << 1 | 1] = lazy[X][v] * (vr - vm);
	lazy[X][v] = -1;
}
void update(int X, int l, int r, int x, int v, int vl, int vr) {
	push(X, v, vl, vr);
	if (l > vr || vl > r) return;
	if (l <= vl && vr <= r) {
		t[X][v] = x * (vr - vl + 1);
		lazy[X][v] = x;
		return;
	}
	int vm = vl + vr >> 1;
	update(X, l, r, x, v << 1, vl, vm);
	update(X, l, r, x, v << 1 | 1, vm + 1, vr);
	t[X][v] = t[X][v << 1] + t[X][v << 1 | 1];
}
void update(int X, int l, int r, int x) {
	update(X, l, r, x, 1, 0, N - 1);
}
int query(int X, int i, int v, int vl, int vr) {
	push(X, v, vl, vr);
	if (vl == vr)
		return t[X][v];
	int vm = vl + vr >> 1, q;
	if (i <= vm)
		q = query(X, i, v << 1, vl, vm);
	else
		q = query(X, i, v << 1 | 1, vm + 1, vr);
	t[X][v] = t[X][v << 1] + t[X][v << 1 | 1];
	return q;
}
int query(int X, int i) {
	return query(X, i, 1, 0, N - 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < N; i++)
		for (int j = 0; j < 4 * N; j++)
			lazy[i][j] = -1;

	int n, m;
	cin >> n >> m;

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char x; cin >> x;
			arr[i][j] = x - '0';
			if (arr[i][j])
				cnt++;
		}
	}
	if (!cnt) {
		cout << 0 << '\n';
		return 0;
	}

	if (n * n * n * m * 12 > 1e6) {
		int a = 0, b = 0;
		for (int i = 0; i < n; i++) {
			int cnt = 0;
			for (int j = 0; j < m; j++) {
				if (arr[i][j] == 1) cnt++;
				else {
					if (cnt)
						a = min(a, cnt);
					cnt = 0;
				}
			}
			if (cnt)
				a = min(a, cnt);
		}
		for (int j = 0; j < m; j++) {
			int cnt = 0;
			for (int i = 0; i < n; i++) {
				if (arr[i][j] == 1) cnt++;
				else {
					if (cnt)
						b = min(b, cnt);
					cnt = 0;
				}
			}
			if (cnt)
				b = min(b, cnt);
		}
		cout << a * 1ll * b << '\n';
		return 0;
	}

	if (n > m) {
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				brr[i][j] = arr[j][i];
			}
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				arr[i][j] = brr[i][j];
			}
		}
		swap(n, m);
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			update(i, j, j, arr[i][j]);
			pref[i][j] = arr[i][j];
			pref[i][j] += (i ? pref[i - 1][j] : 0);
			pref[i][j] += (j ? pref[i][j - 1] : 0);
			pref[i][j] -= (i && j ? pref[i - 1][j - 1] : 0);
		}
	}

	auto get = [&](int a, int b, int c, int d) ->int {
		int s = pref[c][d];
		s -= (a ? pref[a - 1][d] : 0);
		s -= (b ? pref[c][b - 1] : 0);
		s += (a && b ? pref[a - 1][b - 1] : 0);
		return s;
	};

	// brute force

	int Q = 2;
	auto check = [&](int a, int b) ->int {
		for (int i = 0; i + a - 1 < n; i++) {
			for (int j = 0; j + b - 1 < m; j++) {
				int g = get(i, j, i + a - 1, j + b - 1);
				if (g == a * b) {
					for (int x = i; x <= i + a - 1; x++) {
						update(x, j, j + b - 1, Q);
					}
				}
			}
		}
		int ok = 1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (query(i, j) != 0 && query(i, j) != Q)
					ok = 0;
			}
		}
		Q++;
		return ok;
	};

	//O(n*n * 12*m * 12*12)
	//O(10000 *120 * 144)
	//O(1000000)

	long long ans = 0;
	for (int a = 1; a <= n; a++) {
		int l = 1, r = m;
		while (l < r) {
			int b = (l + r + 1) / 2;
			if (check(a, b))
				l = b;
			else
				r = b - 1;
		}
		if (check(a, l))
			ans = max(ans, a * 1ll * l);
	}
	cout << ans << '\n';

	return 0;
}

Compilation message (stderr)

bomb.cpp: In function 'void push(int, int, int, int)':
bomb.cpp:14:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   14 |  int vm = vl + vr >> 1;
      |           ~~~^~~~
bomb.cpp: In function 'void update(int, int, int, int, int, int, int)':
bomb.cpp:27:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  int vm = vl + vr >> 1;
      |           ~~~^~~~
bomb.cpp: In function 'int query(int, int, int, int, int)':
bomb.cpp:39:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int vm = vl + vr >> 1, q;
      |           ~~~^~~~

• Subtask 1: 11 / 100