Submission #235073

#	Time	Username	Problem	Language	Result	Execution time	Memory
235073		UserIsUndefined	Rectangles (IOI19_rect)	C++14	0 / 100	169 ms	284648 KiB

rect

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int kMax = 3000 + 10;

using PII = pair<int, int>;

struct Interval {
	Interval(int key, int start, int end) :
		key(key), start(start), end(end), count(0) {}
	int key, start, end, count = 0;
};

vector<Interval> vertical_intervals, horizontal_intervals;
vector<PII> lookup[kMax][kMax];
vector<int> v, previous;
PII tmp[kMax][kMax];
int a[kMax][kMax];
int n, m;

void FindPrevGreaterOrEqual(const vector<int>& v, int* output) {
	static std::vector<PII> s;
	memset(output, -1, v.size() * sizeof(int));
	s.reserve(v.size());
	s.clear();
	for (int i = 0; i < v.size(); ++i) {
		while(!s.empty() && s.back().first < v[i]) s.pop_back();
		if (!s.empty()) {
			output[i] = s.back().second;
		}
		s.emplace_back(v[i], i);
	}
}

void Summerize(vector<Interval>& intervals) {
	memset(tmp, -1, sizeof tmp);
	for (int i = intervals.size() - 1; i >= 0; --i) {
		auto& interval = intervals[i];
		const int prev = tmp[interval.start][interval.end].first;
		if (prev == interval.key) {
			continue;
		}
		if (prev != interval.key + 1) {
			tmp[interval.start][interval.end].second = 0;
		}
		tmp[interval.start][interval.end].first = interval.key;
		interval.count = ++tmp[interval.start][interval.end].second;
	}
}

long long count_rectangles(std::vector<std::vector<int> > b) {
    n = b.size();
    m = b[0].size();

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			a[i][j] = b[i][j];
		}
	}
	v.resize(m);
	previous.resize(m);
	for (int i = 0; i < n; ++i) {
		copy(a[i], a[i] + m, v.data());
		FindPrevGreaterOrEqual(v, previous.data());
		for (int j = 0; j < m; ++j) {
			if (previous[j] != -1)
			horizontal_intervals.push_back({i, previous[j], j});
		}
		reverse(v.begin(), v.end());
		FindPrevGreaterOrEqual(v, previous.data());
		for (int j = 0; j < m; ++j) {
			if (previous[j] != -1)
				horizontal_intervals.emplace_back(i, m - 1 - j, m - 1 - previous[j]);
		}
	}
	Summerize(horizontal_intervals);

	v.resize(n);
	previous.resize(n);
	for (int j = 0; j < m; ++j) {
		for (int i = 0; i < n; ++i) {
			v[i] = a[i][j];
		}
		FindPrevGreaterOrEqual(v, previous.data());
		for (int i = 0; i < n; ++i) {
			if (previous[i] != -1) vertical_intervals.push_back({j, previous[i], i});
		}
		reverse(v.begin(), v.end());
		FindPrevGreaterOrEqual(v, previous.data());
		for (int i = 0; i < n; ++i) {
			if (previous[i] != -1) {
				vertical_intervals.emplace_back(j, n - 1 - i, n - 1 - previous[i]);
			}
		}
	}
	Summerize(vertical_intervals);

	for (const auto& i : vertical_intervals) {
		lookup[i.start][i.key].emplace_back(i.end, i.count);
	}

	int ans = max(min(2, n) * m, min(2, m) * n);
	for (const auto& interval : horizontal_intervals) {
		if (interval.key == 0) continue;
		for (const auto& p : lookup[interval.key - 1][interval.start + 1]) {
			if (p.first <= interval.key + interval.count &&
					interval.end <= interval.start + 1 + p.second) {
				ans = max(ans, (p.first - interval.key + 2) * (interval.end - interval.start + 1));
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

rect.cpp: In function 'void FindPrevGreaterOrEqual(const std::vector<int>&, int*)':
rect.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); ++i) {
                  ~~^~~~~~~~~~

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