Submission #585369

#	Time	Username	Problem	Language	Result	Execution time	Memory
585369		lumibons	Rectangles (IOI19_rect)	C++17	100 / 100	3488 ms	599384 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

ll count_rectangles(vector<vector<int>> a) {
	int n = (int) a.size(), m = (int) a[0].size();
	vector<vector<int>> cp(n, vector<int>(m, -1)), cn(n, vector<int>(m, -1));
	vector<vector<int>> rp(n, vector<int>(m, -1)), rn(n, vector<int>(m, -1));
	for (int i = 0; i < n; i++) {
		stack<int> s;
		for (int j = 0; j < m; j++) {
			while (!s.empty() && a[i][j] > a[i][s.top()])
				cn[i][s.top()] = j, s.pop();
			if (!s.empty())
				cp[i][j] = a[i][j] < a[i][s.top()] ? s.top() : cp[i][s.top()];
			s.push(j);
		}
	}
	for (int j = 0; j < m; j++) {
		stack<int> s;
		for (int i = 0; i < n; i++) {
			while (!s.empty() && a[i][j] > a[s.top()][j])
				rn[s.top()][j] = i, s.pop();
			if (!s.empty())
				rp[i][j] = a[i][j] < a[s.top()][j] ? s.top() : rp[s.top()][j];
			s.push(i);
		}
	}
	vector<vector<bool>> valid(n, vector<bool>(m, true));
	vector<int> cpr(m * m), cpl(m * m, -2), rpc(n * n, -2), rpl(n * n, -2);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (cp[i][j] != -1 && cn[i][j] != -1 && rp[i][j] != -1 && rn[i][j] != -1) {
				int x = cp[i][j] * m + cn[i][j];
				if (cpl[x] < i - 1)
					cpr[x] = i;
				cpl[x] = i;
				valid[i][j] = valid[i][j] && cpr[x] <= rp[i][j] + 1;
			}
	for (int j = 0; j < m; j++)
		for (int i = 0; i < n; i++)
			if (cp[i][j] != -1 && cn[i][j] != -1 && rp[i][j] != -1 && rn[i][j] != -1) {
				int x = rp[i][j] * n + rn[i][j];
				if (rpl[x] < j - 1)
					rpc[x] = j;
				rpl[x] = j;
				valid[i][j] = valid[i][j] && rpc[x] <= cp[i][j] + 1;
			}
	cpl.assign(m * m, n + 1);
	rpl.assign(n * n, m + 1);
	for (int i = n - 1; i >= 0; i--)
		for (int j = 0; j < m; j++)
			if (cp[i][j] != -1 && cn[i][j] != -1 && rp[i][j] != -1 && rn[i][j] != -1) {
				int x = cp[i][j] * m + cn[i][j];
				if (cpl[x] > i + 1)
					cpr[x] = i;
				cpl[x] = i;
				valid[i][j] = valid[i][j] && cpr[x] >= rn[i][j] - 1;
			}
	for (int j = m - 1; j >= 0; j--)
		for (int i = 0; i < n; i++)
			if (cp[i][j] != -1 && cn[i][j] != -1 && rp[i][j] != -1 && rn[i][j] != -1) {
				int x = rp[i][j] * n + rn[i][j];
				if (rpl[x] > j + 1)
					rpc[x] = j;
				rpl[x] = j;
				valid[i][j] = valid[i][j] && rpc[x] >= cn[i][j] - 1;
			}
	int res = 0;
	unordered_set<ll> rect;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (cp[i][j] != -1 && cn[i][j] != -1 && rp[i][j] != -1 && rn[i][j] != -1 && valid[i][j]) {
				ll x = ((ll) (cp[i][j] * m + cn[i][j]) * n + rp[i][j]) * n + rn[i][j];
				if (rect.find(x) == rect.end())
					res++, rect.insert(x);
			}
	return res;
}

// int main() {
// 	int n = 2500, m = 2500;
// 	vector<vector<int>> a(n, vector<int>(m));
// 	for (int i = 0; i < n; i++)
// 		for (int j = 0; j < m; j++)
// 			a[i][j] = max(i, n - i) + max(j, m - j);
// 	cout << count_rectangles(a) << "\n";
// }

• 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