oj.uz

Submission #415781

# Submission time Handle Problem Language Result Execution time Memory
415781 2021-06-01T13:55:38 Z Mlxa Rectangles (IOI19_rect) C++14
49 / 100
 5000 ms 117952 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "rect.h"

namespace my {

const int N = 1 << 10;
const int INF = 0x3f3f3f3f;

struct st2d {
	int t[2 * N][2 * N];
	void build(int a[N][N]) {
		fill_n(t[0], 4 * N * N, -INF);
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				update(i, j, a[i][j]);
			}
		}
	}
	void update(int i0, int j0, int val) {
		i0 += N, j0 += N;
		for (int i = i0; i > 0; i /= 2) {
			for (int j = j0; j > 0; j /= 2) {
				t[i][j] = max(t[i][j], val);
			}
		}
	}
	int sub(int k, int l, int r) {
		int *arr = t[k];
		int ans = -INF;
		for (; l <= r; l /= 2, r /= 2) {
			if (l % 2 == 1) {
				ans = max(ans, arr[l++]);
			}
			if (r % 2 == 0) {
				ans = max(ans, arr[r--]);
			}
		}
		return ans;
	}
	int query(int li0, int lj0, int ri0, int rj0) {
		int ans = -INF;
		li0 += N, ri0 += N, lj0 += N, rj0 += N;
		for (int li = li0, ri = ri0; li <= ri; li /= 2, ri /= 2) {
			if (li % 2 == 1) {
				ans = max(ans, sub(li++, lj0, rj0));
			}
			if (ri % 2 == 0) {
				ans = max(ans, sub(ri--, lj0, rj0));
			}
		}
		
		// cout << "===" << endl;
		// for (int i = li0; i <= ri0; ++i) {
		// 	for (int j = lj0; j <= rj0; ++j) {
		// 		// cout << "# " << t[i][j] << endl;
		// 		ans = max(ans, t[i][j]);
		// 	}
		// }
		return ans;
		// for (int li = li0, ri = ri0; li <= ri; li = (li + 1) / 2, ri = (ri - 1) / 2) {
		// 	for (int lj = lj0, rj = rj0; lj <= rj; lj = (lj + 1) / 2, rj = (rj - 1) / 2) {
		// 		if (li % 2 == 1 && lj % 2 == 1) {
		// 			ans = max(ans, t[li][lj]);
		// 		}
		// 		if (ri % 2 == 0 && rj % 2 == 0) {
		// 			ans = max(ans, t[ri][rj]);
		// 		}
		// 		if (li % 2 == 1 && rj % 2 == 0) {
		// 			ans = max(ans, )
		// 		}
		// 	}
		// }
		return ans;
	}
} tl, tr, tu, td;

int getmax(int a[N][N], int li, int lj, int ri, int rj) {
	int ans = -(int)1e9;;
	for (int i = li; i <= ri; ++i) {
		for (int j = lj; j <= rj; ++j) {
			ans = max(ans, a[i][j]);
		}
	}
	return ans;
}

int n, m;
int a[N][N];
int l[N][N], r[N][N], u[N][N], d[N][N];
set<tuple<int, int, int, int>> mem;

void dfs(int li, int lj, int ri, int rj) {
	while (1) {
		if (ri > n - 2 || rj > m - 2) {
			return;
		}
		int cl = -tl.query(li, lj, ri, rj);
		if (cl < lj - 1) {
			return;
		}
		int cu = -tu.query(li, lj, ri, rj);
		if (cu < li - 1) {
			return;
		}
		int cr = tr.query(li, lj, ri, rj);
		int cd = td.query(li, lj, ri, rj);
		if (cr <= rj + 1 && cd <= ri + 1) {
			break;
		}
		rj = max(rj, cr - 1);
		ri = max(ri, cd - 1);
	}
	if (!mem.emplace(li, lj, ri, rj).y) {
		return;
	}
	// cout << "add " << li << " " << lj << " " << ri << " " << rj << endl;
	dfs(li, lj, ri + 1, rj);
	dfs(li, lj, ri, rj + 1);
}
}

ll count_rectangles(vector<vector<int>> _a) {
	using namespace my;
	n = (int)_a.size(), m = (int)_a[0].size();
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			a[i][j] = _a[i][j];
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			l[i][j] = j - 1;
			while (l[i][j] >= 0 && a[i][l[i][j]] <= a[i][j]) {
				l[i][j] = l[i][l[i][j]];
			}
			u[i][j] = i - 1;
			while (u[i][j] >= 0 && a[u[i][j]][j] <= a[i][j]) {
				u[i][j] = u[u[i][j]][j];
			}
		}
	}
	for (int i = n - 1; i >= 0; --i) {
		for (int j = m - 1; j >= 0; --j) {
			r[i][j] = j + 1;
			while (r[i][j] < m && a[i][r[i][j]] <= a[i][j]) {
				r[i][j] = r[i][r[i][j]];
			}
			d[i][j] = i + 1;
			while (d[i][j] < n && a[d[i][j]][j] <= a[i][j]) {
				d[i][j] = d[d[i][j]][j];
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			l[i][j] *= -1;
			u[i][j] *= -1;
		}
	}
	tl.build(l);
	tr.build(r);
	tu.build(u);
	td.build(d);
	// for (int i = 0; i < n; ++i) {
	// 	for (int j = 0; j < m; ++j) {
	// 		cout << l[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }
	for (int i = 1; i < n - 1; ++i) {
		for (int j = 1; j < m - 1; ++j) {
			dfs(i, j, i, j);
		}
	}
	return (int)mem.size();
}

#ifdef LC
#include "grader.cpp"
#endif

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 926 ms 66084 KB Output is correct
2 Correct 972 ms 66584 KB Output is correct
3 Correct 985 ms 66516 KB Output is correct
4 Correct 927 ms 66576 KB Output is correct
5 Correct 920 ms 66472 KB Output is correct
6 Correct 913 ms 66580 KB Output is correct
7 Correct 997 ms 66572 KB Output is correct
8 Correct 994 ms 66208 KB Output is correct
9 Correct 952 ms 66472 KB Output is correct
10 Correct 886 ms 66572 KB Output is correct
11 Correct 958 ms 66572 KB Output is correct
12 Correct 963 ms 66512 KB Output is correct
13 Correct 940 ms 65920 KB Output is correct
14 Correct 932 ms 66100 KB Output is correct
15 Correct 938 ms 66168 KB Output is correct
16 Correct 925 ms 66004 KB Output is correct
17 Correct 903 ms 65984 KB Output is correct
18 Correct 973 ms 65888 KB Output is correct
19 Correct 946 ms 66576 KB Output is correct
20 Correct 970 ms 66576 KB Output is correct
21 Correct 1020 ms 66064 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 926 ms 66084 KB Output is correct
2 Correct 972 ms 66584 KB Output is correct
3 Correct 985 ms 66516 KB Output is correct
4 Correct 927 ms 66576 KB Output is correct
5 Correct 920 ms 66472 KB Output is correct
6 Correct 913 ms 66580 KB Output is correct
7 Correct 997 ms 66572 KB Output is correct
8 Correct 994 ms 66208 KB Output is correct
9 Correct 952 ms 66472 KB Output is correct
10 Correct 886 ms 66572 KB Output is correct
11 Correct 958 ms 66572 KB Output is correct
12 Correct 963 ms 66512 KB Output is correct
13 Correct 940 ms 65920 KB Output is correct
14 Correct 932 ms 66100 KB Output is correct
15 Correct 938 ms 66168 KB Output is correct
16 Correct 925 ms 66004 KB Output is correct
17 Correct 903 ms 65984 KB Output is correct
18 Correct 973 ms 65888 KB Output is correct
19 Correct 946 ms 66576 KB Output is correct
20 Correct 970 ms 66576 KB Output is correct
21 Correct 1020 ms 66064 KB Output is correct
22 Correct 992 ms 68016 KB Output is correct
23 Correct 931 ms 68064 KB Output is correct
24 Correct 900 ms 68048 KB Output is correct
25 Correct 951 ms 67612 KB Output is correct
26 Correct 939 ms 67704 KB Output is correct
27 Correct 953 ms 67768 KB Output is correct
28 Correct 925 ms 67780 KB Output is correct
29 Correct 972 ms 67576 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 926 ms 66084 KB Output is correct
2 Correct 972 ms 66584 KB Output is correct
3 Correct 985 ms 66516 KB Output is correct
4 Correct 927 ms 66576 KB Output is correct
5 Correct 920 ms 66472 KB Output is correct
6 Correct 913 ms 66580 KB Output is correct
7 Correct 997 ms 66572 KB Output is correct
8 Correct 994 ms 66208 KB Output is correct
9 Correct 952 ms 66472 KB Output is correct
10 Correct 886 ms 66572 KB Output is correct
11 Correct 958 ms 66572 KB Output is correct
12 Correct 963 ms 66512 KB Output is correct
13 Correct 940 ms 65920 KB Output is correct
14 Correct 932 ms 66100 KB Output is correct
15 Correct 938 ms 66168 KB Output is correct
16 Correct 925 ms 66004 KB Output is correct
17 Correct 992 ms 68016 KB Output is correct
18 Correct 931 ms 68064 KB Output is correct
19 Correct 900 ms 68048 KB Output is correct
20 Correct 951 ms 67612 KB Output is correct
21 Correct 939 ms 67704 KB Output is correct
22 Correct 953 ms 67768 KB Output is correct
23 Correct 925 ms 67780 KB Output is correct
24 Correct 972 ms 67576 KB Output is correct
25 Correct 903 ms 65984 KB Output is correct
26 Correct 973 ms 65888 KB Output is correct
27 Correct 946 ms 66576 KB Output is correct
28 Correct 970 ms 66576 KB Output is correct
29 Correct 1020 ms 66064 KB Output is correct
30 Correct 1014 ms 72996 KB Output is correct
31 Correct 960 ms 72924 KB Output is correct
32 Correct 1094 ms 73056 KB Output is correct
33 Correct 1024 ms 70500 KB Output is correct
34 Correct 1043 ms 71208 KB Output is correct
35 Correct 921 ms 71344 KB Output is correct
36 Correct 940 ms 71328 KB Output is correct
37 Correct 1006 ms 71344 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 926 ms 66084 KB Output is correct
2 Correct 972 ms 66584 KB Output is correct
3 Correct 985 ms 66516 KB Output is correct
4 Correct 927 ms 66576 KB Output is correct
5 Correct 920 ms 66472 KB Output is correct
6 Correct 913 ms 66580 KB Output is correct
7 Correct 997 ms 66572 KB Output is correct
8 Correct 994 ms 66208 KB Output is correct
9 Correct 952 ms 66472 KB Output is correct
10 Correct 886 ms 66572 KB Output is correct
11 Correct 958 ms 66572 KB Output is correct
12 Correct 963 ms 66512 KB Output is correct
13 Correct 940 ms 65920 KB Output is correct
14 Correct 932 ms 66100 KB Output is correct
15 Correct 938 ms 66168 KB Output is correct
16 Correct 925 ms 66004 KB Output is correct
17 Correct 992 ms 68016 KB Output is correct
18 Correct 931 ms 68064 KB Output is correct
19 Correct 900 ms 68048 KB Output is correct
20 Correct 951 ms 67612 KB Output is correct
21 Correct 939 ms 67704 KB Output is correct
22 Correct 953 ms 67768 KB Output is correct
23 Correct 925 ms 67780 KB Output is correct
24 Correct 972 ms 67576 KB Output is correct
25 Correct 1014 ms 72996 KB Output is correct
26 Correct 960 ms 72924 KB Output is correct
27 Correct 1094 ms 73056 KB Output is correct
28 Correct 1024 ms 70500 KB Output is correct
29 Correct 1043 ms 71208 KB Output is correct
30 Correct 921 ms 71344 KB Output is correct
31 Correct 940 ms 71328 KB Output is correct
32 Correct 1006 ms 71344 KB Output is correct
33 Correct 903 ms 65984 KB Output is correct
34 Correct 973 ms 65888 KB Output is correct
35 Correct 946 ms 66576 KB Output is correct
36 Correct 970 ms 66576 KB Output is correct
37 Correct 1020 ms 66064 KB Output is correct
38 Correct 994 ms 85096 KB Output is correct
39 Correct 1060 ms 85096 KB Output is correct
40 Correct 1146 ms 85036 KB Output is correct
41 Correct 1080 ms 85036 KB Output is correct
42 Correct 2176 ms 115664 KB Output is correct
43 Correct 2245 ms 117600 KB Output is correct
44 Correct 2094 ms 117952 KB Output is correct
45 Correct 2033 ms 114612 KB Output is correct
46 Correct 1008 ms 85972 KB Output is correct
47 Correct 1018 ms 87700 KB Output is correct
48 Correct 1140 ms 95944 KB Output is correct
49 Correct 1130 ms 97992 KB Output is correct
50 Correct 1026 ms 88896 KB Output is correct
51 Correct 1103 ms 81980 KB Output is correct
52 Correct 1188 ms 96976 KB Output is correct
53 Correct 1060 ms 97972 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5104 ms 460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 903 ms 65984 KB Output is correct
2 Correct 973 ms 65888 KB Output is correct
3 Correct 946 ms 66576 KB Output is correct
4 Correct 970 ms 66576 KB Output is correct
5 Correct 1020 ms 66064 KB Output is correct
6 Correct 902 ms 66164 KB Output is correct
7 Execution timed out 5059 ms 29344 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 926 ms 66084 KB Output is correct
2 Correct 972 ms 66584 KB Output is correct
3 Correct 985 ms 66516 KB Output is correct
4 Correct 927 ms 66576 KB Output is correct
5 Correct 920 ms 66472 KB Output is correct
6 Correct 913 ms 66580 KB Output is correct
7 Correct 997 ms 66572 KB Output is correct
8 Correct 994 ms 66208 KB Output is correct
9 Correct 952 ms 66472 KB Output is correct
10 Correct 886 ms 66572 KB Output is correct
11 Correct 958 ms 66572 KB Output is correct
12 Correct 963 ms 66512 KB Output is correct
13 Correct 940 ms 65920 KB Output is correct
14 Correct 932 ms 66100 KB Output is correct
15 Correct 938 ms 66168 KB Output is correct
16 Correct 925 ms 66004 KB Output is correct
17 Correct 992 ms 68016 KB Output is correct
18 Correct 931 ms 68064 KB Output is correct
19 Correct 900 ms 68048 KB Output is correct
20 Correct 951 ms 67612 KB Output is correct
21 Correct 939 ms 67704 KB Output is correct
22 Correct 953 ms 67768 KB Output is correct
23 Correct 925 ms 67780 KB Output is correct
24 Correct 972 ms 67576 KB Output is correct
25 Correct 1014 ms 72996 KB Output is correct
26 Correct 960 ms 72924 KB Output is correct
27 Correct 1094 ms 73056 KB Output is correct
28 Correct 1024 ms 70500 KB Output is correct
29 Correct 1043 ms 71208 KB Output is correct
30 Correct 921 ms 71344 KB Output is correct
31 Correct 940 ms 71328 KB Output is correct
32 Correct 1006 ms 71344 KB Output is correct
33 Correct 994 ms 85096 KB Output is correct
34 Correct 1060 ms 85096 KB Output is correct
35 Correct 1146 ms 85036 KB Output is correct
36 Correct 1080 ms 85036 KB Output is correct
37 Correct 2176 ms 115664 KB Output is correct
38 Correct 2245 ms 117600 KB Output is correct
39 Correct 2094 ms 117952 KB Output is correct
40 Correct 2033 ms 114612 KB Output is correct
41 Correct 1008 ms 85972 KB Output is correct
42 Correct 1018 ms 87700 KB Output is correct
43 Correct 1140 ms 95944 KB Output is correct
44 Correct 1130 ms 97992 KB Output is correct
45 Correct 1026 ms 88896 KB Output is correct
46 Correct 1103 ms 81980 KB Output is correct
47 Correct 1188 ms 96976 KB Output is correct
48 Correct 1060 ms 97972 KB Output is correct
49 Execution timed out 5104 ms 460 KB Time limit exceeded
50 Halted 0 ms 0 KB -