Submission #832192

#	Time	Username	Problem	Language	Result	Execution time	Memory
832192		tranxuanbach	Rectangles (IOI19_rect)	C++17	100 / 100	2805 ms	555512 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_l[N][N];
int nxt_r[N][N];
int nxt_u[N][N];
int nxt_d[N][N];
vector <rectangle> candidates;
vector <bool> possible;

// In the u direction
int extend_l[N][N];
int extend_r[N][N];
// In the l direction
int extend_u[N][N];
int extend_d[N][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(i, 1, n){
		ForE(j, 1, m){
			extend_l[i][j] = extend_r[i][j] = i;
		}
		if (not (1 <= i - 1)){
			continue;
		}
		ForE(j, 1, m){
			int k = nxt_l[i][j];
			if (not (1 <= k)){
				continue;
			}
			if (nxt_l[i - 1][j] == k){
				extend_l[i][j] = min(extend_l[i][j], extend_l[i - 1][j]);
			}
			if (nxt_r[i - 1][k] == j){
				extend_l[i][j] = min(extend_l[i][j], extend_r[i - 1][k]);
			}
		}
		ForE(j, 1, m){
			int k = nxt_r[i][j];
			if (not (k <= m)){
				continue;
			}
			if (nxt_r[i - 1][j] == k){
				extend_r[i][j] = min(extend_r[i][j], extend_r[i - 1][j]);
			}
			if (nxt_l[i - 1][k] == j){
				extend_r[i][j] = min(extend_r[i][j], extend_l[i - 1][k]);
			}
		}
	}
	ForE(j, 1, m){
		ForE(i, 1, n){
			extend_u[i][j] = extend_d[i][j] = j;
		}
		if (not (1 <= j - 1)){
			continue;
		}
		ForE(i, 1, n){
			int k = nxt_u[i][j];
			if (not (1 <= k)){
				continue;
			}
			if (nxt_u[i][j - 1] == k){
				extend_u[i][j] = min(extend_u[i][j], extend_u[i][j - 1]);
			}
			if (nxt_d[k][j - 1] == i){
				extend_u[i][j] = min(extend_u[i][j], extend_d[k][j - 1]);
			}
		}
		ForE(i, 1, n){
			int k = nxt_d[i][j];
			if (not (k <= n)){
				continue;
			}
			if (nxt_d[i][j - 1] == k){
				extend_d[i][j] = min(extend_d[i][j], extend_d[i][j - 1]);
			}
			if (nxt_u[k][j - 1] == i){
				extend_d[i][j] = min(extend_d[i][j], extend_u[k][j - 1]);
			}
		}
	}

	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];
		{
			bool ok = false;
			if (nxt_l[x2][y2 + 1] == y1 - 1){
				ok |= (extend_l[x2][y2 + 1] <= x1);
			}
			if (nxt_r[x2][y1 - 1] == y2 + 1){
				ok |= (extend_r[x2][y1 - 1] <= x1);
			}
			possible[i] = possible[i] & ok;
		}
		{
			bool ok = false;
			if (nxt_u[x2 + 1][y2] == x1 - 1){
				ok |= (extend_u[x2 + 1][y2] <= y1);
			}
			if (nxt_d[x1 - 1][y2] == x2 + 1){
				ok |= (extend_d[x1 - 1][y2] <= y1);
			}
			possible[i] = possible[i] & ok;
		}
	}

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