Submission #1241593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241593		The_Samurai	Rectangles (IOI19_rect)	C++20	13 / 100	238 ms	74104 KiB

rect

#include "rect.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;

const int N = 700;

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size(), m = a[0].size();
	// vector<basic_string<vector<short>>> pref1(m, vector<vector<short>>(n, vector<short>(n)));
	ll ans = 0;
	vector<vector<int>> pref(n + 1, vector<int>(m + 1));
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
		pref[i][j] = a[i - 1][j - 1] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
	}
	auto get = [&](int x1, int y1, int x2, int y2) -> int {
		return pref[x2][y2] - pref[x2][y1 - 1] - pref[x1 - 1][y2] + pref[x1 - 1][y1 - 1];
	};
	auto full = [&](int x1, int y1, int x2, int y2) -> int {
		int sum = pref[x2][y2] - pref[x2][y1 - 1] - pref[x1 - 1][y2] + pref[x1 - 1][y1 - 1];
		return sum == (x2 - x1 + 1) * (y2 - y1 + 1);
	};

	for (int i = 2; i < n; i++) for (int j = 2; j < m; j++) {
		if (a[i - 1][j - 1]) continue;
		int lx = j, rx = m - 1, best1 = -1, best2 = -1;
		while (lx <= rx) {
			int mid = (lx + rx) >> 1;
			if (get(i, j, i, mid) == 0) {
				best2 = mid;
				lx = mid + 1;
			} else {
				rx = mid - 1;
			}
		}
		lx = i, rx = n - 1;
		while (lx <= rx) {
			int mid = (lx + rx) >> 1;
			if (get(i, j, mid, j) == 0) {
				best1 = mid;
				lx = mid + 1;
			} else {
				rx = mid - 1;
			}
		}
		// cout << i << ' ' << j << ' ' << best1 << ' ' << best2 << endl;
		assert(best1 != -1 and best2 != -1);
		if (get(i, j, best1, best2)) continue;
		if (!full(i - 1, j, i - 1, best2)) continue;
		if (!full(best1 + 1, j, best1 + 1, best2)) continue;
		if (!full(i, j - 1, best1, j - 1)) continue;
		if (!full(i, best2 + 1, best1, best2 + 1)) continue;
		ans++;
	}

	return ans;
}

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