oj.uz

Submission #524314

# Submission time Handle Problem Language Result Execution time Memory
524314 2022-02-09T04:02:34 Z boykut Bomb (IZhO17_bomb) C++14
26 / 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];
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;
	
	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);
	}

	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)

	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 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
26.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 102468 KB Output is correct
2 Correct 38 ms 102604 KB Output is correct
3 Correct 57 ms 112512 KB Output is correct
4 Correct 55 ms 112620 KB Output is correct
5 Correct 50 ms 102476 KB Output is correct
6 Correct 45 ms 102568 KB Output is correct
7 Correct 40 ms 102592 KB Output is correct
8 Correct 45 ms 102988 KB Output is correct
9 Correct 45 ms 102980 KB Output is correct
10 Correct 41 ms 102812 KB Output is correct
11 Correct 47 ms 102960 KB Output is correct
12 Correct 42 ms 102800 KB Output is correct
13 Correct 39 ms 102748 KB Output is correct
14 Correct 48 ms 102860 KB Output is correct
15 Correct 43 ms 102944 KB Output is correct
16 Correct 60 ms 102952 KB Output is correct
17 Correct 369 ms 104152 KB Output is correct
18 Correct 254 ms 104396 KB Output is correct
19 Correct 589 ms 104952 KB Output is correct
20 Correct 659 ms 105156 KB Output is correct
21 Correct 283 ms 103876 KB Output is correct
22 Correct 485 ms 104468 KB Output is correct
23 Execution timed out 1069 ms 105072 KB Time limit exceeded
24 Correct 505 ms 104752 KB Output is correct
25 Execution timed out 1099 ms 105028 KB Time limit exceeded
26 Execution timed out 1095 ms 105024 KB Time limit exceeded
27 Execution timed out 1105 ms 111832 KB Time limit exceeded
28 Execution timed out 1095 ms 111304 KB Time limit exceeded
29 Execution timed out 1096 ms 114424 KB Time limit exceeded
30 Execution timed out 1096 ms 116004 KB Time limit exceeded
31 Execution timed out 1105 ms 112964 KB Time limit exceeded
32 Execution timed out 1106 ms 116532 KB Time limit exceeded
33 Execution timed out 1106 ms 116680 KB Time limit exceeded
34 Execution timed out 1061 ms 111208 KB Time limit exceeded
35 Execution timed out 1090 ms 116660 KB Time limit exceeded
36 Execution timed out 1106 ms 116716 KB Time limit exceeded
37 Correct 51 ms 102980 KB Output is correct
38 Runtime error 167 ms 131076 KB Execution killed with signal 9
39 Correct 53 ms 102980 KB Output is correct
40 Runtime error 182 ms 131076 KB Execution killed with signal 9
41 Correct 52 ms 102980 KB Output is correct
42 Execution timed out 1071 ms 105028 KB Time limit exceeded
43 Runtime error 172 ms 131076 KB Execution killed with signal 9
44 Execution timed out 1098 ms 116736 KB Time limit exceeded
45 Runtime error 172 ms 131076 KB Execution killed with signal 9
46 Runtime error 171 ms 131076 KB Execution killed with signal 9
47 Runtime error 169 ms 131076 KB Execution killed with signal 9
48 Runtime error 167 ms 131076 KB Execution killed with signal 9
49 Runtime error 176 ms 131076 KB Execution killed with signal 9
50 Runtime error 166 ms 131076 KB Execution killed with signal 9
51 Runtime error 161 ms 131076 KB Execution killed with signal 9
52 Runtime error 173 ms 131076 KB Execution killed with signal 9
53 Runtime error 164 ms 131076 KB Execution killed with signal 9
54 Runtime error 167 ms 131076 KB Execution killed with signal 9
55 Runtime error 169 ms 131076 KB Execution killed with signal 9
56 Runtime error 162 ms 131076 KB Execution killed with signal 9
57 Runtime error 166 ms 131076 KB Execution killed with signal 9
58 Runtime error 171 ms 131076 KB Execution killed with signal 9
59 Runtime error 170 ms 131076 KB Execution killed with signal 9
60 Runtime error 165 ms 131076 KB Execution killed with signal 9
61 Runtime error 164 ms 131076 KB Execution killed with signal 9
62 Runtime error 169 ms 131076 KB Execution killed with signal 9
63 Runtime error 165 ms 131076 KB Execution killed with signal 9
64 Runtime error 166 ms 131076 KB Execution killed with signal 9
65 Runtime error 173 ms 131076 KB Execution killed with signal 9
66 Runtime error 168 ms 131076 KB Execution killed with signal 9
67 Runtime error 165 ms 131076 KB Execution killed with signal 9
68 Runtime error 177 ms 131076 KB Execution killed with signal 9
69 Runtime error 175 ms 131076 KB Execution killed with signal 9
70 Runtime error 171 ms 131076 KB Execution killed with signal 9
71 Runtime error 167 ms 131076 KB Execution killed with signal 9
72 Runtime error 169 ms 131076 KB Execution killed with signal 9
73 Runtime error 164 ms 131076 KB Execution killed with signal 9
74 Runtime error 173 ms 131076 KB Execution killed with signal 9
75 Runtime error 172 ms 131076 KB Execution killed with signal 9
76 Runtime error 173 ms 131076 KB Execution killed with signal 9
77 Runtime error 164 ms 131076 KB Execution killed with signal 9
78 Runtime error 171 ms 131076 KB Execution killed with signal 9
79 Runtime error 175 ms 131076 KB Execution killed with signal 9
80 Runtime error 167 ms 131076 KB Execution killed with signal 9
81 Runtime error 182 ms 131076 KB Execution killed with signal 9
82 Runtime error 169 ms 131076 KB Execution killed with signal 9
83 Runtime error 165 ms 131076 KB Execution killed with signal 9
84 Runtime error 178 ms 131076 KB Execution killed with signal 9
85 Runtime error 167 ms 131076 KB Execution killed with signal 9
86 Runtime error 167 ms 131076 KB Execution killed with signal 9
87 Runtime error 179 ms 131076 KB Execution killed with signal 9
88 Runtime error 164 ms 131076 KB Execution killed with signal 9
89 Runtime error 171 ms 131076 KB Execution killed with signal 9
90 Runtime error 177 ms 131076 KB Execution killed with signal 9
91 Runtime error 162 ms 131076 KB Execution killed with signal 9
92 Runtime error 166 ms 131076 KB Execution killed with signal 9
93 Runtime error 174 ms 131076 KB Execution killed with signal 9
94 Runtime error 169 ms 131076 KB Execution killed with signal 9
95 Runtime error 166 ms 131076 KB Execution killed with signal 9
96 Runtime error 170 ms 131076 KB Execution killed with signal 9
97 Runtime error 166 ms 131076 KB Execution killed with signal 9
98 Runtime error 172 ms 131076 KB Execution killed with signal 9
99 Runtime error 177 ms 131076 KB Execution killed with signal 9
100 Runtime error 167 ms 131076 KB Execution killed with signal 9