제출 #429744

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429744		KoD	Rectangles (IOI19_rect)	C++17	100 / 100	3048 ms	617816 KiB

rect

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

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

struct Fenwick {
	Vec<int> data;
	explicit Fenwick(const int n): data(n + 1) {}
	void add(int i, const int x) {
		i += 1;
		while (i < (int) data.size()) {
			data[i] += x;
			i += i & -i;
		}
	}
	int get(int i) const {
		int x = 0;
		while (i > 0) {
			x += data[i];
			i -= i & -i;
		}
		return x;
	}
	int fold(const int l, const int r) const {
		return get(r) - get(l);
	}
};

ll count_rectangles(Vec<Vec<int>> a) {
	const int n = (int) a.size();
	const int m = (int) a[0].size();
	if (n <= 2 or m <= 2) {
		return 0;
	}
	Vec<Vec<Vec<int>>> row(n, Vec<Vec<int>>(m)), col(n, Vec<Vec<int>>(m));
	for (int i = 0; i < n; ++i) {
		Vec<int> stack;
		for (int j = 0; j < m; ++j) {
			int max = 0;
			while (!stack.empty()) {
				const int k = stack.back();
				if (std::min(a[i][k], a[i][j]) > max and j - k > 1) {
					row[i][j].push_back(k);
				}
				if (a[i][k] >= a[i][j]) {
					break;
				}
				max = std::max(max, a[i][k]);
				stack.pop_back();
			}
			stack.push_back(j);
		}
	}
	for (int j = 0; j < m; ++j) {
		Vec<int> stack;
		for (int i = 0; i < n; ++i) {
			int max = 0;
			while (!stack.empty()) {
				const int k = stack.back();
				if (std::min(a[k][j], a[i][j]) > max and i - k > 1) {
					col[i][j].push_back(k);
				}
				if (a[k][j] >= a[i][j]) {
					break;
				}
				max = std::max(max, a[k][j]);
				stack.pop_back();
			}
			stack.push_back(i);
		}
	}
	Vec<Fenwick> fen(n, Fenwick(m));
	Vec<Vec<std::pair<int, int>>> cand(m);
	for (int j = 0; j < m; ++j) {
		for (const int k : row[1][j]) {
			cand[j].emplace_back(k, 1);
		}
	}
	ll ret = 0;
	for (int i = 2; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			for (const int k : col[i][j]) {
				fen[k].add(j, 1);
			}
			for (const auto [a, l] : cand[j]) {
				for (const int k : col[i][j - 1]) {
					if (i - k - 1 > l) {
						break;
					}
					if (fen[k].fold(a + 1, j) == j - a - 1) {
						ret += 1;
					}
				}
			}
		}
		for (int j = 0; j < m; ++j) {
			for (const int k : col[i][j]) {
				fen[k].add(j, -1);
			}
			Vec<std::pair<int, int>> next;
			const auto& cur = cand[j];
			const auto& add = row[i][j];
			int x = 0, y = 0;
			while (y < (int) add.size()) {
				if (x < (int) cur.size() and cur[x].first == add[y]) {
					next.emplace_back(cur[x].first, cur[x].second + 1);
					x += 1;
					y += 1;
				} else if (x < (int) cur.size() and cur[x].first > add[y]) {
					x += 1;
				} else {
					next.emplace_back(add[y], 1);
					y += 1;
				}
			}
			cand[j] = std::move(next);			
		}
	}
	return ret;
}

• 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