Submission #1078224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078224		Boas	Rectangles (IOI19_rect)	C++17	13 / 100	630 ms	397836 KiB

rect

#include "rect.h"

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define sz(x) (int)x.size()
#define pb push_back
#define loop(x, i) for (int i = 0; i < x; i++)
#define rev(x, i) for (int i = (int)x - 1; i >= 0; i--)
#define ALL(x) begin(x), end(x)
typedef signed i32;
typedef pair<int, int> ii;
typedef vector<i32> vi32;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vi32> vvi32;
typedef vector<vii> vvii;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;

long long count_rectangles(vvi a)
{
	int n = sz(a);	  // h
	int m = sz(a[0]); // w
	vvi fill(n, vi(m, -1));
	vvi nextR1(n, vi(m, -1));
	vvi nextD1(n, vi(m, -1));
	long long res = 0;
	rev(m, c)
	{
		int r1 = n;
		rev(n, r)
		{
			if (a[r][c] == 1)
			{
				r1 = r;
			}
			nextD1[r][c] = r1;
		}
	}
	rev(n, r)
	{
		int c1 = n;
		rev(m, c)
		{
			if (a[r][c] == 1)
			{
				c1 = c;
			}
			nextR1[r][c] = c1;
		}
	}
	rev(m, c)
	{
		int r1 = n;
		rev(n, r)
		{
			if (a[r][c] == 1)
			{
				r1 = r;
			}
			nextD1[r][c] = r1;
		}
	}
	vi cnt;
	auto dfs = [&](auto &&self, int r, int c, int nr) -> bool
	{
		if (r < 0 || c < 0)
			return 1;
		if (r > n - 1 || c > m - 1)
			return 1;
		if (a[r][c] == 1)
			return 0;
		if (fill[r][c] == nr)
			return 0;
		bool res = 0;
		if (r == 0 || c == 0 || r == n - 1 || c == m - 1)
			res = 1;
		fill[r][c] = nr;
		cnt[nr]++;
		res |= self(self, r - 1, c, nr);
		res |= self(self, r + 1, c, nr);
		res |= self(self, r, c - 1, nr);
		res |= self(self, r, c + 1, nr);
		return res;
	};
	int i = -1;
	for (int c = 0; c < m; c++)
	{
		for (int r = 0; r < n; r++)
		{
			if (a[r][c] == 0 && fill[r][c] == -1)
			{
				i++;
				int endr = nextD1[r][c];
				int endc = nextR1[r][c];
				cnt.pb(0);
				if (dfs(dfs, r, c, i))
					continue;
				if (cnt[i] != (endr - r) * (endc - c))
					continue;
				bool val = 1;
				for (int c2 = c; c2 < endc; c2++)
				{
					if (!val)
						break;
					for (int r2 = r; r2 < endr; r2++)
					{
						if (fill[r2][c2] != i)
						{
							val = 0;
							break;
						}
					}
				}
				if (val)
					res++;
			}
		}
	}
	return res;
}

• 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