Submission #420586

#	Time	Username	Problem	Language	Result	Execution time	Memory
420586		KoD	Rectangles (IOI19_rect)	C++17	10 / 100	2 ms	500 KiB

rect

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

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

ll count_rectangles(Vec<Vec<int>> a) {
	const int n = (int) a.size();
	const int m = (int) a[0].size();
	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) {
			while (!stack.empty() and a[i][stack.back()] < a[i][j]) {
				if (stack.back() + 1 < j) {
					cand[i].emplace_back(stack.back(), j);
				}
				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)) {
					// std::cerr << u << ' ' << d << ' ' << l << ' ' << r << std::endl;
					ret += 1;
				}
			}
		}
	}
	return ret;
}

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