Submission #420711

#	Time	Username	Problem	Language	Result	Execution time	Memory
420711		KoD	Rectangles (IOI19_rect)	C++17	59 / 100	1911 ms	78732 KiB

rect

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

using ll = long long;
template <class T> using Vec = std::vector<T>;

struct UnionFind {
	Vec<int> par;
	UnionFind(const int n): par(n, -1) {}
	int find(const int x) {
		return par[x] < 0 ? x : par[x] = find(par[x]);
	}
	void merge(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;
		if (par[x] > par[y]) {
			std::swap(x, y);
		}
		par[x] += par[y];
		par[y] = x;
	}
};

ll count_rectangles(Vec<Vec<int>> a) {
	const int n = (int) a.size();
	const int m = (int) a[0].size();
	if (n <= 3 or (n <= 700 and m <= 700)) {
		Vec<Vec<std::pair<int, int>>> cand(n);
		for (int i = 0; i < n; ++i) {
			Vec<int> stack;
			for (int j = 0; j < m; ++j) {
				int max = 0;
				while (!stack.empty() and a[i][stack.back()] < a[i][j]) {
					if (stack.back() + 1 < j and max < a[i][stack.back()]) {
						cand[i].emplace_back(stack.back(), j);
					}
					max = std::max(max, a[i][stack.back()]);
					stack.pop_back();
				}
				if (!stack.empty() and stack.back() + 1 < j) {
					cand[i].emplace_back(stack.back(), j);
				}
				stack.push_back(j);
			}
			std::sort(cand[i].begin(), cand[i].end());
		}
		ll ret = 0;
		for (int u = 0; u < n; ++u) {
			Vec<int> max(m);
			Vec<int> ok(m + 1);
			Vec<std::pair<int, int>> pair;
			for (int d = u + 2; d < n; ++d) {
				for (int j = 0; j < m; ++j) {
					max[j] = std::max(max[j], a[d - 1][j]);
					ok[j + 1] = ok[j] + (max[j] < std::min(a[u][j], a[d][j]));
				}
				if (d == u + 2) {
					pair = cand[d - 1];
				} else {
					Vec<std::pair<int, int>> next;
					const auto& add = cand[d - 1];
					int l = 0, r = 0;
					while (l < (int) pair.size() and r < (int) add.size()) {
						if (pair[l] < add[r]) {
							l += 1;
						} else if (add[r] < pair[l]) {
							r += 1;
						} else {
							next.emplace_back(pair[l]);
							l += 1;
							r += 1;
						}
					}
					pair = std::move(next);
				}
				for (const auto [l, r]: pair) {
					if (ok[r] - ok[l + 1] == r - (l + 1)) {
						ret += 1;
					}
				}
			}
		}
		return ret;
	}
	else {
		UnionFind dsu(n * m);
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (a[i][j] == 0) {
					if (i > 0 and a[i - 1][j] == 0) {
						dsu.merge((i - 1) * m + j, i * m + j);
					}
					if (j > 0 and a[i][j - 1] == 0) {
						dsu.merge(i * m + (j - 1), i * m + j);
					}
				}
			}
		}
		Vec<int> u(n * m, n), d(n * m, -1), l(n * m, m), r(n * m, -1);
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				const int k = dsu.find(i * m + j);
				u[k] = std::min(u[k], i);
				d[k] = std::max(d[k], i);
				l[k] = std::min(l[k], j);
				r[k] = std::max(r[k], j);
			}
		}
		ll ret = 0;
		for (int k = 0; k < n * m; ++k) {
			if (u[k] == n or u[k] == 0 or d[k] == n - 1 or l[k] == 0 or r[k] == m - 1) {
				continue;
			}
			if ((d[k] - u[k] + 1) * (r[k] - l[k] + 1) == -dsu.par[k]) {
				ret += 1;
			}
		}
		return ret;
	}
}

• 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