Submission #832174

#	Time	Username	Problem	Language	Result	Execution time	Memory
832174		tranxuanbach	Rectangles (IOI19_rect)	C++17	72 / 100	5085 ms	331736 KiB

rect

#include "rect.h"

#include <bits/stdc++.h>
using namespace std;

#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define isz(a) ((signed)a.size())

using ll = long long;

struct rectangle{
	int x1, y1, x2, y2;

	friend bool operator< (const rectangle& lhs, const rectangle& rhs){
		if (lhs.x1 != rhs.x1) return lhs.x1 < rhs.x1;
		if (lhs.y1 != rhs.y1) return lhs.y1 < rhs.y1;
		if (lhs.x2 != rhs.x2) return lhs.x2 < rhs.x2;
		return lhs.y2 < rhs.y2;
	}

	friend bool operator== (const rectangle& lhs, const rectangle& rhs){
		return lhs.x1 == rhs.x1 and lhs.y1 == rhs.y1 and lhs.x2 == rhs.x2 and lhs.y2 == rhs.y2;
	}
};

const int N = 2500 + 5;
const int inf = 1e8 + 7;

int n, m;
int a[N][N];

int nxt_u[N][N];
int nxt_l[N][N];
int nxt_r[N][N];
int nxt_d[N][N];
vector <rectangle> candidates;
vector <bool> possible;

int tmp[N];

ll count_rectangles(vector <vector <int>> _a){
	n = isz(_a);
	m = isz(_a.front());
	ForE(i, 0, n + 1){
		ForE(j, 0, m + 1){
			if (i == 0 or i == n + 1 or j == 0 or j == m + 1){
				a[i][j] = inf;
				continue;
			}
			a[i][j] = _a[i - 1][j - 1];
		}
	}

	ForE(i, 1, n){
		vector <int> st = {0};
		ForE(j, 1, m){
			while (a[i][st.back()] < a[i][j]){
				st.pop_back();
			}
			nxt_l[i][j] = st.back();
			st.emplace_back(j);
		}
		st = {m + 1};
		FordE(j, m, 1){
			while (a[i][st.back()] < a[i][j]){
				st.pop_back();
			}
			nxt_r[i][j] = st.back();
			st.emplace_back(j);
		}
	}
	ForE(j, 1, m){
		vector <int> st = {0};
		ForE(i, 1, n){
			while (a[st.back()][j] < a[i][j]){
				st.pop_back();
			}
			nxt_u[i][j] = st.back();
			st.emplace_back(i);
		}
		st = {n + 1};
		FordE(i, n, 1){
			while (a[st.back()][j] < a[i][j]){
				st.pop_back();
			}
			nxt_d[i][j] = st.back();
			st.emplace_back(i);
		}
	}

	ForE(x, 2, n - 1){
		ForE(y, 2, m - 1){
			{ // ul corner is SS
				int tx = nxt_d[x - 1][y] - 1, ty = nxt_r[x][y - 1] - 1;
				if (x <= tx and tx <= n - 1 and y <= ty and ty <= m - 1){
					candidates.emplace_back(rectangle{x, y, tx, ty});
				}
			}
			{ // ur corner is SS
				int tx = nxt_d[x - 1][y] - 1, ty = nxt_l[x][y + 1] + 1;
				if (x <= tx and tx <= n - 1 and 2 <= ty and ty <= y){
					candidates.emplace_back(rectangle{x, ty, tx, y});
				}
			}
			{ // dl corner is SS
				int tx = nxt_u[x + 1][y] + 1, ty = nxt_r[x][y - 1] - 1;
				if (2 <= tx and tx <= x and y <= ty and ty <= m - 1){
					candidates.emplace_back(rectangle{tx, y, x, ty});
				}
			}
			{ // dr corner is SS
				int tx = nxt_u[x + 1][y] + 1, ty = nxt_l[x][y + 1] + 1;
				if (2 <= tx and tx <= x and 2 <= ty and ty <= y){
					candidates.emplace_back(rectangle{tx, ty, x, y});
				}
			}
			{ // dr corner is SL
				int tx = nxt_u[x + 1][y] + 1, ty = nxt_l[tx][y + 1] + 1;
				if (2 <= tx and tx <= x and 2 <= ty and ty <= y){
					candidates.emplace_back(rectangle{tx, ty, x, y});
				}
			}
			{ // dr corner is LS
				int ty = nxt_l[x][y + 1] + 1, tx = nxt_u[x + 1][ty] + 1;
				if (2 <= tx and tx <= x and 2 <= ty and ty <= y){
					candidates.emplace_back(rectangle{tx, ty, x, y});
				}
			}
		}
	}
	sort(candidates.begin(), candidates.end());
	candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());
	possible.assign(isz(candidates), true);
	For(i, 0, isz(candidates)){
		auto &[x1, y1, x2, y2] = candidates[i];
		// cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
		ForE(y, y1, y2){
			if (nxt_d[x1 - 1][y] != x2 + 1 and nxt_u[x2 + 1][y] != x1 - 1){
				possible[i] = false;
				break;
			}
		}
		if (not possible[i]){
			continue;
		}
		ForE(x, x1, x2){
			if (nxt_r[x][y1 - 1] != y2 + 1 and nxt_l[x][y2 + 1] != y1 - 1){
				possible[i] = false;
				break;
			}
		}
	}
	return accumulate(possible.begin(), possible.end(), 0);
}

• 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