Submission #790975

#	Time	Username	Problem	Language	Result	Execution time	Memory
790975		erekle	Rectangles (IOI19_rect)	C++17	100 / 100	4037 ms	765160 KiB

rect

#include "rect.h"
#include <iostream>
#include <stack>
#include <tuple>

using namespace std;

enum direction { Left, Right, Up, Down };
int dr[]{0, 0, -1, +1}, dc[]{-1, +1, 0, 0};

const int N = 2500, LG = 12;
int maxP2[1+N]{};

long long count_rectangles(vector<vector<int>> a) {
	int n = a.size(), m = a[0].size();

	vector<vector<int>> reach[4]; // distance to closest in each direction that is greater than or equal to
	for (int d = 0; d < 4; ++d) reach[d].assign(n, vector<int>(m));
	for (int i = 0; i < n; ++i) { // row
		{ // left
			stack<int> candidates;
			for (int j = 0; j < m; ++j) {
				while (!candidates.empty() && a[i][candidates.top()] < a[i][j]) candidates.pop();
				reach[0][i][j] = candidates.empty() ? -1 : candidates.top();
				reach[0][i][j] = j - reach[0][i][j];
				candidates.push(j);
			}
		}
		{ // right
			stack<int> candidates;
			for (int j = m-1; j >= 0; --j) {
				while (!candidates.empty() && a[i][candidates.top()] < a[i][j]) candidates.pop();
				reach[1][i][j] = candidates.empty() ? m : candidates.top();
				reach[1][i][j] = reach[1][i][j] - j;
				candidates.push(j);
			}
		}
	}
	for (int j = 0; j < m; ++j) { // column
		{ // up
			stack<int> candidates;
			for (int i = 0; i < n; ++i) {
				while (!candidates.empty() && a[candidates.top()][j] < a[i][j]) candidates.pop();
				reach[2][i][j] = candidates.empty() ? -1 : candidates.top();
				reach[2][i][j] = i - reach[2][i][j];
				candidates.push(i);
			}
		}
		{ // down
			stack<int> candidates;
			for (int i = n-1; i >= 0; --i) {
				while (!candidates.empty() && a[candidates.top()][j] < a[i][j]) candidates.pop();
				reach[3][i][j] = candidates.empty() ? n : candidates.top();
				reach[3][i][j] = reach[3][i][j] - i;
				candidates.push(i);
			}
		}
	}
	
	/* The letters below represent values just outside the border of the rectangle, adjacent to corners of the rectangle
	     a     e
		.-------.
	   c|		|d
		|		|
		|		|
		.-------.
		 b     f
	*/
	
	vector<tuple<int, int, int, int>> rectangles;
	auto consider = [&](int i, int j, int h, int w) { // rectangle with given top left position, width, height
		if (i <= 0 || j <= 0 || i+h-1 >= n-1 || j+w-1 >= m-1) return;
		if ( w < 1 || h < 1) return;
		// check that all sides can reach one another
		// if (RMQ(Right, j-1, i, i+h-1) <= w) return;
		// if (RMQ(Left, j+w, i, i+h-1) <= w) return;
		// if (RMQ(Down, i-1, j, j+w-1) <= h) return;
		// if (RMQ(Up, i+h, j, j+w-1) <= h) return;
		// ++rectangles;
		rectangles.emplace_back(i, j, h, w);
	};
	for (int i = 1; i < n-1; ++i) {
		for (int j = 1; j < m-1; ++j) {
			{ // Case 1: a <= b && c <= d: consider i, j as top left
				int height = reach[Down][i-1][j] - 1, width = reach[Right][i][j-1] - 1;
				consider(i, j, height, width);
			}

			{ // Case 2: a <= b && c > d: consider i, j as top right
				int width = reach[Left][i][j+1] - 1;
				int jLeft = j-width+1;
				if (jLeft > 0 && a[i][jLeft-1] > a[i][j+1]) { // c > d, not equal
					int height = reach[Down][i-1][jLeft] - 1;
					consider(i, jLeft, height, width);
				}
			}

			{ // Case 3: a > b && c <= d: consider i, j as bottom left
				int height = reach[Up][i+1][j] - 1;
				int iTop = i-height+1;
				if (iTop > 0 && a[iTop-1][j] > a[i+1][j]) { // a > b, not equal
					int width = reach[Right][iTop][j-1] - 1;
					consider(iTop, j, height, width);
				}
			}

			{ // Case 4: a > b && c > d && e <= f: consider i, j, as top right
				int height = reach[Down][i-1][j] - 1, width = reach[Left][i][j+1] - 1;
				int iBottom = i+height-1, jLeft = j-width+1;
				if (iBottom+1 < n && jLeft > 0) {
					// check that a > b and c > d
					if (a[i-1][jLeft] > a[iBottom+1][jLeft] && a[i][jLeft-1] > a[i][j+1]) {
						consider(i, jLeft, height, width);
					}
				}
			}

			{ // Case 5: a > b && c > d && e > f: consider i, j as bottom right
				int height = reach[Up][i+1][j] - 1;
				int iTop = i-height+1;
				if (iTop > 0 && a[iTop-1][j] > a[i+1][j]) { // e > f, not equal
					int width = reach[Left][iTop][j+1] - 1;
					int jLeft = j-width+1;
					// check that a > b and c > d
					if (a[iTop-1][jLeft] > a[i+1][jLeft] && a[iTop][jLeft-1] > a[iTop][j+1]) {
						consider(iTop, jLeft, height, width);
					}
				}
			}
		}
	}
	
	// test reach in all four directions separately to reduce memory usage by a factor of 4
	
	// maxP2
	for (int i = 2; i <= max(n, m); ++i) maxP2[i] = maxP2[i-1] + !(i & (i-1));

	vector<vector<int>> reachRMQ[1+LG];
	for (int k = 0; k <= LG; ++k) reachRMQ[k].assign(n, vector<int>(m));
	auto RMQ = [&](int dir, int rc, int l, int r) {
		int p2 = maxP2[r-l+1];
		if (dir == 0 || dir == 1) {
			int j = rc;
			return min(reachRMQ[p2][l][j], reachRMQ[p2][r-(1<<p2)+1][j]);
		} else {
			int i = rc;
			return min(reachRMQ[p2][i][l], reachRMQ[p2][i][r-(1<<p2)+1]);
		}
	};

	vector<tuple<int, int, int, int>> rectangles2;

	// Left
	for (int j = 0; j < m; ++j) { // column
		for (int i = 0; i < n; ++i) reachRMQ[0][i][j] = reach[0][i][j];
		for (int k = 1; k <= LG; ++k) {
			for (int i = 0; i < n; ++i) {
				int i2 = i + (1 << (k-1));
				if (i2 >= n) {
					reachRMQ[k][i][j] = reachRMQ[k-1][i][j];
				} else {
					reachRMQ[k][i][j] = min(reachRMQ[k-1][i][j], reachRMQ[k-1][i + (1 << (k-1))][j]);
				}
			}
		}
	}
	rectangles2.clear();
	for (auto [i, j, h, w] : rectangles) {
		if (RMQ(Left, j+w, i, i+h-1) > w) rectangles2.emplace_back(i, j, h, w);
	}
	rectangles = rectangles2;

	// Right
	for (int k = 0; k <= LG; ++k) reachRMQ[k].assign(n, vector<int>(m));
	for (int j = 0; j < m; ++j) { // column
		for (int i = 0; i < n; ++i) reachRMQ[0][i][j] = reach[1][i][j];
		for (int k = 1; k <= LG; ++k) {
			for (int i = 0; i < n; ++i) {
				int i2 = i + (1 << (k-1));
				if (i2 >= n) {
					reachRMQ[k][i][j] = reachRMQ[k-1][i][j];
				} else {
					reachRMQ[k][i][j] = min(reachRMQ[k-1][i][j], reachRMQ[k-1][i + (1 << (k-1))][j]);
				}
			}
		}
	}
	rectangles2.clear();
	for (auto [i, j, h, w] : rectangles) {
		if (RMQ(Right, j-1, i, i+h-1) > w) rectangles2.emplace_back(i, j, h, w);
	}
	rectangles = rectangles2;

	// Up
	for (int i = 0; i < n; ++i) { // row
		for (int j = 0; j < m; ++j) reachRMQ[0][i][j] = reach[2][i][j];
		for (int k = 1; k <= LG; ++k) {
			for (int j = 0; j < m; ++j) {
				int j2 = j + (1 << (k-1));
				if (j2 >= m) {
					reachRMQ[k][i][j] = reachRMQ[k-1][i][j];
				} else {
					reachRMQ[k][i][j] = min(reachRMQ[k-1][i][j], reachRMQ[k-1][i][j + (1 << (k-1))]);
				}
			}
		}
	}
	rectangles2.clear();
	for (auto [i, j, h, w] : rectangles) {
		if (RMQ(Up, i+h, j, j+w-1) > h) rectangles2.emplace_back(i, j, h, w);
	}
	rectangles = rectangles2;

	// Down
	for (int i = 0; i < n; ++i) { // row
		for (int j = 0; j < m; ++j) reachRMQ[0][i][j] = reach[3][i][j];
		for (int k = 1; k <= LG; ++k) {
			for (int j = 0; j < m; ++j) {
				int j2 = j + (1 << (k-1));
				if (j2 >= m) {
					reachRMQ[k][i][j] = reachRMQ[k-1][i][j];
				} else {
					reachRMQ[k][i][j] = min(reachRMQ[k-1][i][j], reachRMQ[k-1][i][j + (1 << (k-1))]);
				}
			}
		}
	}
	rectangles2.clear();
	for (auto [i, j, h, w] : rectangles) {
		if (RMQ(Down, i-1, j, j+w-1) > h) rectangles2.emplace_back(i, j, h, w);
	}
	rectangles = rectangles2;
	
	return rectangles.size();
}

• 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