oj.uz

Submission #524308

# Submission time Handle Problem Language Result Execution time Memory
524308 2022-02-09T03:44:40 Z boykut Bomb (IZhO17_bomb) C++14
26 / 100
 1000 ms 131076 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;
	
	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++) {
			char x; cin >> x;
			st[i].update(j, j, x - '0');
			arr[i][j] = x - '0';
			pref[i][j] = x - '0';
			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
26.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Execution timed out 1087 ms 20684 KB Time limit exceeded
4 Execution timed out 1092 ms 20684 KB Time limit exceeded
5 Correct 11 ms 332 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 3 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 320 KB Output is correct
11 Correct 3 ms 460 KB Output is correct
12 Correct 1 ms 448 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 460 KB Output is correct
16 Correct 7 ms 460 KB Output is correct
17 Correct 165 ms 972 KB Output is correct
18 Correct 86 ms 960 KB Output is correct
19 Correct 334 ms 1324 KB Output is correct
20 Correct 332 ms 1296 KB Output is correct
21 Correct 98 ms 844 KB Output is correct
22 Correct 223 ms 1220 KB Output is correct
23 Correct 559 ms 1404 KB Output is correct
24 Correct 256 ms 1180 KB Output is correct
25 Correct 885 ms 1404 KB Output is correct
26 Execution timed out 1085 ms 1356 KB Time limit exceeded
27 Execution timed out 1067 ms 5708 KB Time limit exceeded
28 Execution timed out 1074 ms 5872 KB Time limit exceeded
29 Execution timed out 1084 ms 7648 KB Time limit exceeded
30 Execution timed out 1098 ms 8900 KB Time limit exceeded
31 Execution timed out 1094 ms 6980 KB Time limit exceeded
32 Execution timed out 1087 ms 8132 KB Time limit exceeded
33 Execution timed out 1090 ms 9340 KB Time limit exceeded
34 Execution timed out 1056 ms 5316 KB Time limit exceeded
35 Execution timed out 1057 ms 9432 KB Time limit exceeded
36 Execution timed out 1083 ms 9284 KB Time limit exceeded
37 Correct 3 ms 460 KB Output is correct
38 Runtime error 59 ms 131076 KB Execution killed with signal 9
39 Correct 4 ms 460 KB Output is correct
40 Execution timed out 1079 ms 28092 KB Time limit exceeded
41 Correct 5 ms 460 KB Output is correct
42 Execution timed out 1080 ms 1356 KB Time limit exceeded
43 Runtime error 60 ms 131076 KB Execution killed with signal 9
44 Execution timed out 1041 ms 9268 KB Time limit exceeded
45 Runtime error 58 ms 131076 KB Execution killed with signal 9
46 Runtime error 52 ms 131076 KB Execution killed with signal 9
47 Runtime error 66 ms 131076 KB Execution killed with signal 9
48 Runtime error 59 ms 131076 KB Execution killed with signal 9
49 Runtime error 57 ms 131076 KB Execution killed with signal 9
50 Runtime error 61 ms 131076 KB Execution killed with signal 9
51 Runtime error 60 ms 131076 KB Execution killed with signal 9
52 Runtime error 61 ms 131076 KB Execution killed with signal 9
53 Runtime error 61 ms 131076 KB Execution killed with signal 9
54 Runtime error 57 ms 131076 KB Execution killed with signal 9
55 Runtime error 58 ms 131076 KB Execution killed with signal 9
56 Runtime error 64 ms 131076 KB Execution killed with signal 9
57 Runtime error 56 ms 131076 KB Execution killed with signal 9
58 Runtime error 59 ms 131076 KB Execution killed with signal 9
59 Runtime error 60 ms 131076 KB Execution killed with signal 9
60 Runtime error 63 ms 131076 KB Execution killed with signal 9
61 Runtime error 57 ms 131076 KB Execution killed with signal 9
62 Runtime error 62 ms 131076 KB Execution killed with signal 9
63 Runtime error 58 ms 131076 KB Execution killed with signal 9
64 Runtime error 58 ms 131076 KB Execution killed with signal 9
65 Runtime error 59 ms 131076 KB Execution killed with signal 9
66 Runtime error 58 ms 131076 KB Execution killed with signal 9
67 Runtime error 58 ms 131076 KB Execution killed with signal 9
68 Runtime error 59 ms 131076 KB Execution killed with signal 9
69 Runtime error 57 ms 131076 KB Execution killed with signal 9
70 Execution timed out 1075 ms 107620 KB Time limit exceeded
71 Runtime error 59 ms 131076 KB Execution killed with signal 9
72 Runtime error 61 ms 131076 KB Execution killed with signal 9
73 Runtime error 59 ms 131076 KB Execution killed with signal 9
74 Runtime error 65 ms 131076 KB Execution killed with signal 9
75 Runtime error 59 ms 131076 KB Execution killed with signal 9
76 Runtime error 57 ms 131076 KB Execution killed with signal 9
77 Runtime error 60 ms 131076 KB Execution killed with signal 9
78 Runtime error 60 ms 131076 KB Execution killed with signal 9
79 Runtime error 59 ms 131076 KB Execution killed with signal 9
80 Runtime error 58 ms 131076 KB Execution killed with signal 9
81 Runtime error 60 ms 131076 KB Execution killed with signal 9
82 Runtime error 59 ms 131076 KB Execution killed with signal 9
83 Runtime error 67 ms 131076 KB Execution killed with signal 9
84 Runtime error 60 ms 131076 KB Execution killed with signal 9
85 Runtime error 65 ms 131076 KB Execution killed with signal 9
86 Runtime error 57 ms 131076 KB Execution killed with signal 9
87 Runtime error 60 ms 131076 KB Execution killed with signal 9
88 Runtime error 58 ms 131076 KB Execution killed with signal 9
89 Runtime error 60 ms 131076 KB Execution killed with signal 9
90 Execution timed out 1037 ms 107628 KB Time limit exceeded
91 Runtime error 61 ms 131076 KB Execution killed with signal 9
92 Runtime error 65 ms 131076 KB Execution killed with signal 9
93 Runtime error 59 ms 131076 KB Execution killed with signal 9
94 Runtime error 57 ms 131076 KB Execution killed with signal 9
95 Runtime error 62 ms 131076 KB Execution killed with signal 9
96 Runtime error 58 ms 131076 KB Execution killed with signal 9
97 Runtime error 59 ms 131076 KB Execution killed with signal 9
98 Runtime error 61 ms 131076 KB Execution killed with signal 9
99 Runtime error 64 ms 131076 KB Execution killed with signal 9
100 Runtime error 62 ms 131076 KB Execution killed with signal 9