Submission #790960

#	Time	Username	Problem	Language	Result	Execution time	Memory
790960		erekle	Rectangles (IOI19_rect)	C++17	59 / 100	1947 ms	1048576 KiB

rect

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

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);
			}
		}
	}
	
	// maxP2
	for (int i = 2; i <= max(n, m); ++i) maxP2[i] = maxP2[i-1] + !(i & (i-1));

	vector<vector<int>> reachRMQ[4][1+LG];
	for (int d = 0; d < 4; ++d) {
		for (int k = 0; k <= LG; ++k) reachRMQ[d][k].assign(n, vector<int>(m));
	}
	for (int i = 0; i < n; ++i) { // row
		for (int j = 0; j < m; ++j) {
			reachRMQ[2][0][i][j] = reach[2][i][j];
			reachRMQ[3][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[2][k][i][j] = reachRMQ[2][k-1][i][j];
					reachRMQ[3][k][i][j] = reachRMQ[3][k-1][i][j];
				} else {
					reachRMQ[2][k][i][j] = min(reachRMQ[2][k-1][i][j], reachRMQ[2][k-1][i][j + (1 << (k-1))]);
					reachRMQ[3][k][i][j] = min(reachRMQ[3][k-1][i][j], reachRMQ[3][k-1][i][j + (1 << (k-1))]);
				}
			}
		}
	}
	for (int j = 0; j < m; ++j) { // column
		for (int i = 0; i < n; ++i) {
			reachRMQ[0][0][i][j] = reach[0][i][j];
			reachRMQ[1][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[0][k][i][j] = reachRMQ[0][k-1][i][j];
					reachRMQ[1][k][i][j] = reachRMQ[1][k-1][i][j];
				} else {
					reachRMQ[0][k][i][j] = min(reachRMQ[0][k-1][i][j], reachRMQ[0][k-1][i + (1 << (k-1))][j]);
					reachRMQ[1][k][i][j] = min(reachRMQ[1][k-1][i][j], reachRMQ[1][k-1][i + (1 << (k-1))][j]);
				}
			}
		}
	}

	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[dir][p2][l][j], reachRMQ[dir][p2][r-(1<<p2)+1][j]);
		} else {
			int i = rc;
			return min(reachRMQ[dir][p2][i][l], reachRMQ[dir][p2][i][r-(1<<p2)+1]);
		}
	};

	/* The letters below represent values just outside the border of the rectangle, adjacent to corners of the rectangle
	     a     e
		.-------.
	   c|		|d
		|		|
		|		|
		.-------.
		 b     f
	*/
	
	int rectangles = 0;
	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;
	};
	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);
					}
				}
			}
		}
	}
	return rectangles;
}

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