oj.uz

Submission #524313

# Submission time Handle Problem Language Result Execution time Memory
524313 2022-02-09T03:59:30 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);

	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 0 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 21 ms 10444 KB Output is correct
4 Correct 22 ms 10564 KB Output is correct
5 Correct 13 ms 428 KB Output is correct
6 Correct 7 ms 332 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 6 ms 1100 KB Output is correct
9 Correct 7 ms 1100 KB Output is correct
10 Correct 2 ms 844 KB Output is correct
11 Correct 6 ms 1100 KB Output is correct
12 Correct 3 ms 844 KB Output is correct
13 Correct 2 ms 836 KB Output is correct
14 Correct 4 ms 972 KB Output is correct
15 Correct 5 ms 972 KB Output is correct
16 Correct 19 ms 1100 KB Output is correct
17 Correct 349 ms 3040 KB Output is correct
18 Correct 218 ms 3148 KB Output is correct
19 Correct 559 ms 4096 KB Output is correct
20 Correct 671 ms 4356 KB Output is correct
21 Correct 202 ms 2592 KB Output is correct
22 Correct 442 ms 3576 KB Output is correct
23 Execution timed out 1079 ms 4556 KB Time limit exceeded
24 Correct 452 ms 3788 KB Output is correct
25 Execution timed out 1096 ms 4556 KB Time limit exceeded
26 Execution timed out 1096 ms 4556 KB Time limit exceeded
27 Execution timed out 1096 ms 14608 KB Time limit exceeded
28 Execution timed out 1091 ms 14796 KB Time limit exceeded
29 Execution timed out 1091 ms 18468 KB Time limit exceeded
30 Execution timed out 1094 ms 22468 KB Time limit exceeded
31 Execution timed out 1094 ms 17484 KB Time limit exceeded
32 Execution timed out 1090 ms 21956 KB Time limit exceeded
33 Execution timed out 1092 ms 23620 KB Time limit exceeded
34 Execution timed out 1094 ms 13516 KB Time limit exceeded
35 Execution timed out 1085 ms 23620 KB Time limit exceeded
36 Execution timed out 1093 ms 23620 KB Time limit exceeded
37 Correct 10 ms 1100 KB Output is correct
38 Runtime error 683 ms 131076 KB Execution killed with signal 9
39 Correct 10 ms 1100 KB Output is correct
40 Execution timed out 1073 ms 55908 KB Time limit exceeded
41 Correct 12 ms 1100 KB Output is correct
42 Execution timed out 1081 ms 4556 KB Time limit exceeded
43 Runtime error 681 ms 131076 KB Execution killed with signal 9
44 Execution timed out 1094 ms 23620 KB Time limit exceeded
45 Runtime error 684 ms 131076 KB Execution killed with signal 9
46 Runtime error 713 ms 131076 KB Execution killed with signal 9
47 Runtime error 709 ms 131076 KB Execution killed with signal 9
48 Runtime error 681 ms 131076 KB Execution killed with signal 9
49 Runtime error 675 ms 131076 KB Execution killed with signal 9
50 Runtime error 696 ms 131076 KB Execution killed with signal 9
51 Runtime error 670 ms 131076 KB Execution killed with signal 9
52 Runtime error 679 ms 131076 KB Execution killed with signal 9
53 Runtime error 694 ms 131076 KB Execution killed with signal 9
54 Runtime error 673 ms 131076 KB Execution killed with signal 9
55 Runtime error 698 ms 131076 KB Execution killed with signal 9
56 Runtime error 702 ms 131076 KB Execution killed with signal 9
57 Runtime error 691 ms 131076 KB Execution killed with signal 9
58 Runtime error 691 ms 131076 KB Execution killed with signal 9
59 Runtime error 694 ms 131076 KB Execution killed with signal 9
60 Runtime error 683 ms 131076 KB Execution killed with signal 9
61 Runtime error 691 ms 131076 KB Execution killed with signal 9
62 Runtime error 687 ms 131076 KB Execution killed with signal 9
63 Runtime error 693 ms 131076 KB Execution killed with signal 9
64 Runtime error 685 ms 131076 KB Execution killed with signal 9
65 Runtime error 694 ms 131076 KB Execution killed with signal 9
66 Runtime error 678 ms 131076 KB Execution killed with signal 9
67 Runtime error 678 ms 131076 KB Execution killed with signal 9
68 Runtime error 687 ms 131076 KB Execution killed with signal 9
69 Runtime error 695 ms 131076 KB Execution killed with signal 9
70 Runtime error 601 ms 131076 KB Execution killed with signal 9
71 Runtime error 681 ms 131076 KB Execution killed with signal 9
72 Runtime error 706 ms 131076 KB Execution killed with signal 9
73 Runtime error 676 ms 131076 KB Execution killed with signal 9
74 Runtime error 676 ms 131076 KB Execution killed with signal 9
75 Runtime error 683 ms 131076 KB Execution killed with signal 9
76 Runtime error 729 ms 131076 KB Execution killed with signal 9
77 Runtime error 689 ms 131076 KB Execution killed with signal 9
78 Runtime error 692 ms 131076 KB Execution killed with signal 9
79 Runtime error 706 ms 131076 KB Execution killed with signal 9
80 Runtime error 691 ms 131076 KB Execution killed with signal 9
81 Runtime error 695 ms 131076 KB Execution killed with signal 9
82 Runtime error 685 ms 131076 KB Execution killed with signal 9
83 Runtime error 698 ms 131076 KB Execution killed with signal 9
84 Runtime error 681 ms 131076 KB Execution killed with signal 9
85 Runtime error 709 ms 131076 KB Execution killed with signal 9
86 Runtime error 712 ms 131076 KB Execution killed with signal 9
87 Runtime error 697 ms 131076 KB Execution killed with signal 9
88 Runtime error 682 ms 131076 KB Execution killed with signal 9
89 Runtime error 684 ms 131076 KB Execution killed with signal 9
90 Runtime error 606 ms 131076 KB Execution killed with signal 9
91 Runtime error 712 ms 131076 KB Execution killed with signal 9
92 Runtime error 693 ms 131076 KB Execution killed with signal 9
93 Runtime error 697 ms 131076 KB Execution killed with signal 9
94 Runtime error 686 ms 131076 KB Execution killed with signal 9
95 Runtime error 674 ms 131076 KB Execution killed with signal 9
96 Runtime error 680 ms 131076 KB Execution killed with signal 9
97 Runtime error 686 ms 131076 KB Execution killed with signal 9
98 Runtime error 688 ms 131076 KB Execution killed with signal 9
99 Runtime error 687 ms 131076 KB Execution killed with signal 9
100 Runtime error 696 ms 131076 KB Execution killed with signal 9