oj.uz

Submission #524312

# Submission time Handle Problem Language Result Execution time Memory
524312 2022-02-09T03:53:33 Z boykut Bomb (IZhO17_bomb) C++14
28 / 100
 1000 ms 131076 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 15 ms 10464 KB Output is correct
4 Correct 14 ms 10444 KB Output is correct
5 Correct 9 ms 332 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 460 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 460 KB Output is correct
16 Correct 5 ms 460 KB Output is correct
17 Correct 69 ms 972 KB Output is correct
18 Correct 40 ms 1228 KB Output is correct
19 Correct 116 ms 1484 KB Output is correct
20 Correct 133 ms 1560 KB Output is correct
21 Correct 35 ms 844 KB Output is correct
22 Correct 81 ms 972 KB Output is correct
23 Correct 296 ms 1404 KB Output is correct
24 Correct 104 ms 1384 KB Output is correct
25 Correct 586 ms 1400 KB Output is correct
26 Execution timed out 1088 ms 1356 KB Time limit exceeded
27 Execution timed out 1077 ms 6732 KB Time limit exceeded
28 Execution timed out 1085 ms 5836 KB Time limit exceeded
29 Execution timed out 1088 ms 8516 KB Time limit exceeded
30 Execution timed out 1091 ms 8660 KB Time limit exceeded
31 Execution timed out 1083 ms 6796 KB Time limit exceeded
32 Execution timed out 1088 ms 9848 KB Time limit exceeded
33 Execution timed out 1092 ms 9156 KB Time limit exceeded
34 Execution timed out 1097 ms 6476 KB Time limit exceeded
35 Execution timed out 1100 ms 9096 KB Time limit exceeded
36 Execution timed out 1092 ms 9156 KB Time limit exceeded
37 Correct 2 ms 460 KB Output is correct
38 Runtime error 136 ms 131076 KB Execution killed with signal 9
39 Correct 3 ms 492 KB Output is correct
40 Execution timed out 1097 ms 27428 KB Time limit exceeded
41 Correct 3 ms 460 KB Output is correct
42 Execution timed out 1084 ms 1356 KB Time limit exceeded
43 Runtime error 139 ms 131076 KB Execution killed with signal 9
44 Execution timed out 1096 ms 9132 KB Time limit exceeded
45 Runtime error 142 ms 131076 KB Execution killed with signal 9
46 Runtime error 137 ms 131076 KB Execution killed with signal 9
47 Runtime error 136 ms 131076 KB Execution killed with signal 9
48 Runtime error 140 ms 131076 KB Execution killed with signal 9
49 Runtime error 136 ms 131076 KB Execution killed with signal 9
50 Runtime error 143 ms 131076 KB Execution killed with signal 9
51 Runtime error 136 ms 131076 KB Execution killed with signal 9
52 Runtime error 141 ms 131076 KB Execution killed with signal 9
53 Runtime error 131 ms 131076 KB Execution killed with signal 9
54 Runtime error 138 ms 131076 KB Execution killed with signal 9
55 Runtime error 145 ms 131076 KB Execution killed with signal 9
56 Runtime error 142 ms 131076 KB Execution killed with signal 9
57 Runtime error 137 ms 131076 KB Execution killed with signal 9
58 Runtime error 147 ms 131076 KB Execution killed with signal 9
59 Runtime error 141 ms 131076 KB Execution killed with signal 9
60 Runtime error 144 ms 131076 KB Execution killed with signal 9
61 Runtime error 152 ms 131076 KB Execution killed with signal 9
62 Runtime error 138 ms 131076 KB Execution killed with signal 9
63 Runtime error 136 ms 131076 KB Execution killed with signal 9
64 Runtime error 142 ms 131076 KB Execution killed with signal 9
65 Runtime error 137 ms 131076 KB Execution killed with signal 9
66 Runtime error 134 ms 131076 KB Execution killed with signal 9
67 Runtime error 142 ms 131076 KB Execution killed with signal 9
68 Runtime error 141 ms 131076 KB Execution killed with signal 9
69 Runtime error 159 ms 131076 KB Execution killed with signal 9
70 Execution timed out 1097 ms 104600 KB Time limit exceeded
71 Runtime error 179 ms 131076 KB Execution killed with signal 9
72 Runtime error 138 ms 131076 KB Execution killed with signal 9
73 Runtime error 140 ms 131076 KB Execution killed with signal 9
74 Runtime error 152 ms 131076 KB Execution killed with signal 9
75 Runtime error 145 ms 131076 KB Execution killed with signal 9
76 Runtime error 144 ms 131076 KB Execution killed with signal 9
77 Runtime error 144 ms 131076 KB Execution killed with signal 9
78 Runtime error 139 ms 131076 KB Execution killed with signal 9
79 Runtime error 133 ms 131076 KB Execution killed with signal 9
80 Runtime error 139 ms 131076 KB Execution killed with signal 9
81 Runtime error 142 ms 131076 KB Execution killed with signal 9
82 Runtime error 141 ms 131076 KB Execution killed with signal 9
83 Runtime error 138 ms 131076 KB Execution killed with signal 9
84 Runtime error 146 ms 131076 KB Execution killed with signal 9
85 Runtime error 141 ms 131076 KB Execution killed with signal 9
86 Runtime error 136 ms 131076 KB Execution killed with signal 9
87 Runtime error 144 ms 131076 KB Execution killed with signal 9
88 Runtime error 141 ms 131076 KB Execution killed with signal 9
89 Runtime error 138 ms 131076 KB Execution killed with signal 9
90 Execution timed out 1097 ms 104588 KB Time limit exceeded
91 Runtime error 135 ms 131076 KB Execution killed with signal 9
92 Runtime error 144 ms 131076 KB Execution killed with signal 9
93 Runtime error 143 ms 131076 KB Execution killed with signal 9
94 Runtime error 143 ms 131076 KB Execution killed with signal 9
95 Runtime error 141 ms 131076 KB Execution killed with signal 9
96 Runtime error 138 ms 131076 KB Execution killed with signal 9
97 Runtime error 139 ms 131076 KB Execution killed with signal 9
98 Runtime error 138 ms 131076 KB Execution killed with signal 9
99 Runtime error 140 ms 131076 KB Execution killed with signal 9
100 Runtime error 144 ms 131076 KB Execution killed with signal 9