Submission #524312

#	Time	Username	Problem	Language	Result	Execution time	Memory
524312		boykut	Bomb (IZhO17_bomb)	C++14	28 / 100	1100 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];

class segment_tree {
public:
	segment_tree() {
	}
	void build(size_t s) {
		n = 1;
		while (n < s) n <<= 1;
		t.assign(2 * n + 1, 0);
		lazy.assign(2 * n + 1, 0);
	}
	void push(int v, int vl, int vr) {
		if (vl == vr || lazy[v] == -1) return;
		lazy[v << 1] = lazy[v];
		lazy[v << 1 | 1] = lazy[v];
		int vm = vl + vr >> 1;
		t[v << 1] = lazy[v] * (vm - vl + 1);
		t[v << 1 | 1] = lazy[v] * (vr - vm);
		lazy[v] = -1;
	}
	void update(int l, int r, int x, int v, int vl, int vr) {
		push(v, vl, vr);
		if (l > vr || vl > r) return;
		if (l <= vl && vr <= r) {
			t[v] = x * (vr - vl + 1);
			lazy[v] = x;
			return;
		}
		int vm = vl + vr >> 1;
		update(l, r, x, v << 1, vl, vm);
		update(l, r, x, v << 1 | 1, vm + 1, vr);
		t[v] = t[v << 1] + t[v << 1 | 1];
	}
	void update(int l, int r, int x) {
		update(l, r, x, 1, 0, n - 1);
	}
	int query(int i, int v, int vl, int vr) {
		push(v, vl, vr);
		if (vl == vr)
			return t[v];
		int vm = vl + vr >> 1, q;
		if (i <= vm)
			q = query(i, v << 1, vl, vm);
		else
			q = query(i, v << 1 | 1, vm + 1, vr);
		t[v] = t[v << 1] + t[v << 1 | 1];
		return q;
	}
	int query(int i) {
		return query(i, 1, 0, n - 1);
	}
private:
	int n;
	vector<int> t, lazy;
};

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

	int n, m;
	cin >> n >> m;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char x; cin >> x;
			arr[i][j] = x - '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);
	}

	vector<segment_tree> st(n);
	for (int i = 0; i < n; i++)
		st[i].build(m);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			st[i].update(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++) {
						st[x].update(j, j + b - 1, Q);
					}
				}
			}
		}
		int ok = 1;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (st[i].query(j) != 0 && st[i].query(j) != Q)
					ok = 0;
			}
		}
		Q++;
		return ok;
	};

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

	int 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 * l);
	}
	cout << ans << '\n';

	return 0;
}

Compilation message (stderr)

bomb.cpp: In member function 'void segment_tree::build(size_t)':
bomb.cpp:15:12: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   15 |   while (n < s) n <<= 1;
      |          ~~^~~
bomb.cpp: In member function 'void segment_tree::push(int, int, int)':
bomb.cpp:23:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |   int vm = vl + vr >> 1;
      |            ~~~^~~~
bomb.cpp: In member function 'void segment_tree::update(int, int, int, int, int, int)':
bomb.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |   int vm = vl + vr >> 1;
      |            ~~~^~~~
bomb.cpp: In member function 'int segment_tree::query(int, int, int, int)':
bomb.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int vm = vl + vr >> 1, q;
      |            ~~~^~~~

• Subtask 1: 28 / 100