Submission #607583

#	Time	Username	Problem	Language	Result	Execution time	Memory
607583		Temmie	Rectangles (IOI19_rect)	C++17	100 / 100	4221 ms	561260 KiB

rect

#include <bits/stdc++.h>

inline bool bad(int i, int j, std::vector <std::vector <int>> c[2], std::vector <std::vector <int>> r[2]) {
	return c[0][i][j] == -1 || c[1][i][j] == -1 || r[1][i][j] == -1 || r[0][i][j] == -1;
}

long long count_rectangles(std::vector <std::vector <int>> g) {
	int n = g.size();
	int m = g[0].size();
	std::vector <std::vector <int>> c[2], r[2];
	c[0] = c[1] = r[0] = r[1] = std::vector <std::vector <int>> (n, std::vector <int> (m, -1));
	std::vector <int> v;
	for (int j = 0; j < m; j++, v.clear()) { for (int i = 0; i < n; i++) { int vb; while (v.size() && g[i][j] > g[vb = v.back()][j]) { r[1][vb][j] = i; v.pop_back(); } if (v.size()) { r[0][i][j] = vb; if (g[i][j] >= g[vb][j]) { r[0][i][j] = r[0][vb][j]; } } v.push_back(i); } }
	for (int i = 0; i < n; i++, v.clear()) { for (int j = 0; j < m; j++) { int vb; while (v.size() && g[i][j] > g[i][vb = v.back()]) { c[1][i][vb] = j; v.pop_back(); } if (v.size()) { c[0][i][j] = vb; if (g[i][j] >= g[i][vb]) { c[0][i][j] = c[0][i][vb]; } } v.push_back(j); } }
	bool ok[3000][3000];
	memset(ok, true, sizeof(ok));
	std::vector <int> cc[2] = { std::vector <int> (m * m), std::vector <int> (m * m, -42) }, rr[2] = { std::vector <int> (n * n, -42), std::vector <int> (n * n, -42) };
	for (int i = 0; i < n; i++) { for (int j = 0, ind; j < m; j++) { if (!bad(i, j, c, r)) { if ((cc[1][ind = c[0][i][j] * m + c[1][i][j]]) < i - 1) { cc[0][ind] = i; } cc[1][ind] = i; ok[i][j] &= cc[0][ind] <= r[0][i][j] + 1; } } }
	for (int j = 0; j < m; j++) { for (int i = 0, ind; i < n; i++) { if (!bad(i, j, c, r)) { if ((rr[1][ind = r[0][i][j] * n + r[1][i][j]]) < j - 1) { rr[0][ind] = j; } rr[1][ind] = j; ok[i][j] &= rr[0][ind] <= c[0][i][j] + 1; } } }
	for (int i = 0; i < m; i++) { for (int j = 0; j < m; j++) { cc[1][i * m + j] = n + 1; } }
	for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { rr[1][i * n + j] = m + 1; } }
	for (int i = n - 1; ~i; i--) { for (int j = 0, ind; j < m; j++) { if (!bad(i, j, c, r)) { if ((cc[1][ind = c[0][i][j] * m + c[1][i][j]]) > i + 1) { cc[0][ind] = i; } cc[1][ind] = i; ok[i][j] &= cc[0][ind] >= r[1][i][j] - 1; } } }
	for (int j = m - 1; ~j; j--) { for (int i = 0, ind; i < n; i++) { if (!bad(i, j, c, r)) { if ((rr[1][ind = r[0][i][j] * n + r[1][i][j]]) > j + 1) { rr[0][ind] = j; } rr[1][ind] = j; ok[i][j] &= rr[0][ind] >= c[1][i][j] - 1; } } }
	long long ans = 0;
	std::set <long long> st;
	for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!bad(i, j, c, r) && ok[i][j]) { long long chain = (((long long) c[0][i][j] * m + c[1][i][j]) * n + r[0][i][j]) * n + r[1][i][j]; ans += st.find(chain) == st.end(); st.insert(chain); } } }
	return ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 28 / 28