oj.uz

Submission #524309

# Submission time Handle Problem Language Result Execution time Memory
524309 2022-02-09T03:48:54 Z boykut Bomb (IZhO17_bomb) C++14
28 / 100
 1000 ms 131192 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2500;
int arr[N][N];
int pref[N][N];

class segment_tree {
public:
	segment_tree() {
	}
	segment_tree(size_t s) {
		n = 1;
		while (n < s) n <<= 1;
		t.assign(2 * n, 0);
		lazy = t;
	}
	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 l, int r, int v, int vl, int vr) {
		push(v, vl, vr);
		if (l > vr || vl > r) return 0;
		if (l <= vl && vr <= r) return t[v];
		int vm = vl + vr >> 1;
		int q1 = query(l, r, v << 1, vl, vm);
		int q2 = query(l, r, v << 1 | 1, vm + 1, vr);
		t[v] = t[v << 1] + t[v << 1 | 1];
		return q1 + q2;
	}
	int query(int l, int r) {
		return query(l, r, 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) {
		int brr[m][n];
		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] = segment_tree(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, j) != 0 && st[i].query(j, 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 constructor 'segment_tree::segment_tree(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, int)':
bomb.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int vm = vl + vr >> 1;
      |            ~~~^~~~

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 18 ms 10448 KB Output is correct
4 Correct 18 ms 10440 KB Output is correct
5 Correct 11 ms 332 KB Output is correct
6 Correct 4 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 1 ms 332 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 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 472 KB Output is correct
16 Correct 7 ms 496 KB Output is correct
17 Correct 166 ms 992 KB Output is correct
18 Correct 108 ms 1008 KB Output is correct
19 Correct 262 ms 1244 KB Output is correct
20 Correct 303 ms 1272 KB Output is correct
21 Correct 96 ms 880 KB Output is correct
22 Correct 207 ms 1124 KB Output is correct
23 Correct 586 ms 1388 KB Output is correct
24 Correct 221 ms 1100 KB Output is correct
25 Correct 879 ms 1384 KB Output is correct
26 Execution timed out 1090 ms 1356 KB Time limit exceeded
27 Execution timed out 1026 ms 5580 KB Time limit exceeded
28 Execution timed out 1091 ms 5776 KB Time limit exceeded
29 Execution timed out 1068 ms 7244 KB Time limit exceeded
30 Execution timed out 1091 ms 8644 KB Time limit exceeded
31 Execution timed out 1041 ms 6852 KB Time limit exceeded
32 Execution timed out 1082 ms 8388 KB Time limit exceeded
33 Execution timed out 1090 ms 9036 KB Time limit exceeded
34 Execution timed out 1084 ms 5580 KB Time limit exceeded
35 Execution timed out 1089 ms 9060 KB Time limit exceeded
36 Execution timed out 1084 ms 9028 KB Time limit exceeded
37 Correct 3 ms 460 KB Output is correct
38 Runtime error 131 ms 131076 KB Execution killed with signal 9
39 Correct 4 ms 460 KB Output is correct
40 Execution timed out 1092 ms 27424 KB Time limit exceeded
41 Correct 5 ms 460 KB Output is correct
42 Execution timed out 1083 ms 1356 KB Time limit exceeded
43 Runtime error 138 ms 131076 KB Execution killed with signal 9
44 Execution timed out 1095 ms 9036 KB Time limit exceeded
45 Runtime error 139 ms 131076 KB Execution killed with signal 9
46 Runtime error 134 ms 131076 KB Execution killed with signal 9
47 Runtime error 140 ms 131076 KB Execution killed with signal 9
48 Runtime error 134 ms 131076 KB Execution killed with signal 9
49 Runtime error 144 ms 131076 KB Execution killed with signal 9
50 Runtime error 137 ms 131076 KB Execution killed with signal 9
51 Runtime error 137 ms 131076 KB Execution killed with signal 9
52 Runtime error 156 ms 131076 KB Execution killed with signal 9
53 Runtime error 137 ms 131076 KB Execution killed with signal 9
54 Runtime error 136 ms 131076 KB Execution killed with signal 9
55 Runtime error 136 ms 131076 KB Execution killed with signal 9
56 Runtime error 132 ms 131076 KB Execution killed with signal 9
57 Runtime error 137 ms 131076 KB Execution killed with signal 9
58 Runtime error 140 ms 131076 KB Execution killed with signal 9
59 Runtime error 146 ms 131192 KB Execution killed with signal 9
60 Runtime error 134 ms 131076 KB Execution killed with signal 9
61 Runtime error 142 ms 131076 KB Execution killed with signal 9
62 Runtime error 131 ms 131076 KB Execution killed with signal 9
63 Runtime error 145 ms 131076 KB Execution killed with signal 9
64 Runtime error 134 ms 131076 KB Execution killed with signal 9
65 Runtime error 133 ms 131076 KB Execution killed with signal 9
66 Runtime error 153 ms 131076 KB Execution killed with signal 9
67 Runtime error 137 ms 131076 KB Execution killed with signal 9
68 Runtime error 136 ms 131076 KB Execution killed with signal 9
69 Runtime error 139 ms 131076 KB Execution killed with signal 9
70 Execution timed out 1104 ms 103748 KB Time limit exceeded
71 Runtime error 142 ms 131076 KB Execution killed with signal 9
72 Runtime error 141 ms 131076 KB Execution killed with signal 9
73 Runtime error 150 ms 131076 KB Execution killed with signal 9
74 Runtime error 142 ms 131076 KB Execution killed with signal 9
75 Runtime error 163 ms 131076 KB Execution killed with signal 9
76 Runtime error 140 ms 131076 KB Execution killed with signal 9
77 Runtime error 133 ms 131076 KB Execution killed with signal 9
78 Runtime error 134 ms 131076 KB Execution killed with signal 9
79 Runtime error 137 ms 131076 KB Execution killed with signal 9
80 Runtime error 133 ms 131076 KB Execution killed with signal 9
81 Runtime error 137 ms 131076 KB Execution killed with signal 9
82 Runtime error 133 ms 131076 KB Execution killed with signal 9
83 Runtime error 161 ms 131076 KB Execution killed with signal 9
84 Runtime error 134 ms 131076 KB Execution killed with signal 9
85 Runtime error 137 ms 131076 KB Execution killed with signal 9
86 Runtime error 136 ms 131076 KB Execution killed with signal 9
87 Runtime error 139 ms 131076 KB Execution killed with signal 9
88 Runtime error 142 ms 131076 KB Execution killed with signal 9
89 Runtime error 135 ms 131076 KB Execution killed with signal 9
90 Execution timed out 1095 ms 103772 KB Time limit exceeded
91 Runtime error 141 ms 131076 KB Execution killed with signal 9
92 Runtime error 139 ms 131076 KB Execution killed with signal 9
93 Runtime error 139 ms 131076 KB Execution killed with signal 9
94 Runtime error 135 ms 131076 KB Execution killed with signal 9
95 Runtime error 135 ms 131076 KB Execution killed with signal 9
96 Runtime error 152 ms 131076 KB Execution killed with signal 9
97 Runtime error 133 ms 131076 KB Execution killed with signal 9
98 Runtime error 142 ms 131076 KB Execution killed with signal 9
99 Runtime error 136 ms 131076 KB Execution killed with signal 9
100 Runtime error 131 ms 131076 KB Execution killed with signal 9