Submission #470375

#	Time	Username	Problem	Language	Result	Execution time	Memory
470375		tutis	Rectangles (IOI19_rect)	C++17	72 / 100	5051 ms	441328 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
long long count_rectangles(vector<vector<int> > a) {
	int n = a.size();
	int m = a[0].size();
	vector<vector<int>> j2(n, vector<int>(m, -1));
	vector<vector<int>> j1(n, vector<int>(m, -1));
	vector<vector<int>> i2(n, vector<int>(m, -1));
	vector<vector<int>> i1(n, vector<int>(m, -1));
	for (int i = 0; i < n; i++)
	{
		vector<int>A;
		for (int j = 0; j < m; j++)
		{
			while (A.size() > 0 && a[i][A.back()] < a[i][j])
				A.pop_back();
			if (!A.empty())
				if (A.back() + 1 <= j - 1)
					j1[i][j] = A.back();
			A.push_back(j);
		}
		A.clear();
		for (int j = m - 1; j >= 0; j--)
		{
			while (A.size() > 0 && a[i][A.back()] < a[i][j])
				A.pop_back();
			if (!A.empty())
				if (j + 1 <= A.back() - 1)
					j2[i][j] = A.back();
			A.push_back(j);
		}
	}
	for (int j = 0; j < m; j++)
	{
		vector<int>A;
		for (int i = 0; i < n; i++)
		{
			while (A.size() > 0 && a[A.back()][j] < a[i][j])
				A.pop_back();
			if (!A.empty())
			{
				if (A.back() + 1 <= i - 1)
					i1[i][j] = A.back();
				else
					i1[i][j] = -1;
			}
			else
				i1[i][j] = -1;
			A.push_back(i);
		}
		A.clear();
		for (int i = n - 1; i >= 0; i--)
		{
			while (A.size() > 0 && a[A.back()][j] < a[i][j])
				A.pop_back();
			if (!A.empty())
			{
				if (i + 1 <= A.back() - 1)
					i2[i][j] = A.back();
				else
					i2[i][j] = -1;
			}
			else
				i2[i][j] = -1;
			A.push_back(i);
		}
	}
	vector<vector<int>> dpi1(n, vector<int>(m, n + 1));
	vector<vector<int>> dpi2(n, vector<int>(m, n + 1));
	vector<vector<int>> dpj1(m, vector<int>(n, m + 1));
	vector<vector<int>> dpj2(m, vector<int>(n, m + 1));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int j_ = j2[i][j];
			if (j_ != -1)
			{
				dpi1[i][j] = i;
				if (i != 0)
				{
					if (j2[i - 1][j] == j_)
						dpi1[i][j] = dpi1[i - 1][j];
					if (j1[i - 1][j_] == j)
						dpi1[i][j] = dpi2[i - 1][j_];
				}
			}
		}
		for (int j = m - 1; j >= 0; j--)
		{
			int j_ = j1[i][j];
			if (j_ != -1)
			{
				dpi2[i][j] = i;
				if (i != 0)
				{
					if (j1[i - 1][j] == j_)
						dpi2[i][j] = dpi2[i - 1][j];
					if (j2[i - 1][j_] == j)
						dpi2[i][j] = dpi1[i - 1][j_];
				}
			}
		}
	}
	for (int j = 0; j < m; j++)
	{
		for (int i = 0; i < n; i++)
		{
			int i_ = i2[i][j];
			if (i_ != -1)
			{
				dpj1[j][i] = j;
				if (j != 0)
				{
					if (i2[i][j - 1] == i_)
						dpj1[j][i] = dpj1[j - 1][i];
					if (i1[i_][j - 1] == i)
						dpj1[j][i] = dpj2[j - 1][i_];
				}
			}
		}
		for (int i = n - 1; i >= 0; i--)
		{
			int i_ = i1[i][j];
			if (i_ != -1)
			{
				dpj2[j][i] = j;
				if (j != 0)
				{
					if (i1[i][j - 1] == i_)
						dpj2[j][i] = dpj2[j - 1][i];
					if (i2[i_][j - 1] == i)
						dpj2[j][i] = dpj1[j - 1][i_];
				}
			}
		}
	}
	long long ans = 0;
	set<tuple<int, int, int, int>>S;
	auto check = [&](int x1, int x2, int y1, int y2)->void
	{
		if (x1 == -1 || x2 == -1 || y1 == -1 || y2 == -1)
			return;
		if (S.count({x1, x2, y1, y2}))
		return;
		S.insert({x1, x2, y1, y2});
		for (int i : {x1 + 1, x2 - 1})
		{
			if (j2[i][y1] != y2 && j1[i][y2] != y1)
				return;
		}
		for (int j : {y1 + 1, y2 - 1})
		{
			if (i2[x1][j] != x2 && i1[x2][j] != x1)
				return;
		}
		if (j2[x2 - 1][y1] == y2)
		{
			if (dpi1[x2 - 1][y1] > x1 + 1)
				return;
		}
		else
		{
			if (dpi2[x2 - 1][y2] > x1 + 1)
				return;
		}
		if (i2[x1][y2 - 1] == x2)
		{
			if (dpj1[y2 - 1][x1] > y1 + 1)
				return;
		}
		else
		{
			if (dpj2[y2 - 1][x2] > y1 + 1)
				return;
		}
		ans++;
	};
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (j != 0 && j != m - 1)
				for (int i_ : {i1[i][j], i2[i][j]})
				{
					if (i_ == -1)
						continue;
					int x1 = i;
					int x2 = i_;
					if (x1 > x2)
						swap(x1, x2);
					check(x1, x2, j - 1, j2[x1 + 1][j - 1]);
					check(x1, x2, j1[x1 + 1][j + 1], j + 1);
				}
		}
	}
	return ans;
}
// int main()
// {
// 	cout << count_rectangles({{1, 1, 1}, {1, 0, 1}, {1, 1, 1}}) << endl;
// }

• 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: 0 / 28