Submission #171197

#	Time	Username	Problem	Language	Result	Execution time	Memory
171197		nobik	Rectangles (IOI19_rect)	C++14	72 / 100	5115 ms	453192 KiB

rect

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

using namespace std;

vector<vector<pair<int, int>>> CalcSegments(const vector<int>& a) {
	int n = static_cast<int>(a.size());
	vector<vector<pair<int, int>>> segments(n);
	vector<int> s;
	for (int i = 0; i < n; ++i) {
		while (!s.empty()) {
			int segment = i - s.back() - 1;
			if (segment > 0) 
				segments[i].emplace_back(segment, 1);
			if (a[s.back()] >= a[i]) 
				break;
			s.pop_back();
		}

		if (!s.empty() && a[s.back()] == a[i])
			s.pop_back();

		s.push_back(i);
	}

	segments.shrink_to_fit();
	return segments;
}

vector<pair<int, int>> Merge(const vector<pair<int, int>>& a, const vector<pair<int, int>>& b) {
	vector<pair<int, int>> r;
	int a_size = static_cast<int>(a.size());
	int j = 0;
	for (const auto& e: b) {
		while (j < a_size && a[j].first < e.first) {
			++j;
		}

		int cnt = e.second;
		if (j < a_size && a[j].first == e.first) {
			cnt += a[j].second;
		}

		r.emplace_back(e.first, cnt);
	}

	return r;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = static_cast<int>(a.size());
	int m = static_cast<int>(a.front().size());

	vector<vector<vector<pair<int, int>>>> horizontal_segments(n, vector<vector<pair<int, int>>>(m));
	vector<vector<vector<pair<int, int>>>> vertical_segments(n, vector<vector<pair<int, int>>>(m));

	for (int i = 0; i < n; ++i) {
		horizontal_segments[i] = CalcSegments(a[i]);
	}

	for (int j = 0; j < m; ++j) {
		vector<int> b;
		for (int i = 0; i < n; ++i) {
			b.push_back(a[i][j]);
		}

		auto segments = CalcSegments(b);
		for (int i = 0; i < n; ++i) {
			vertical_segments[i][j] = segments[i];
		}
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (i > 0) horizontal_segments[i][j] = Merge(horizontal_segments[i - 1][j], horizontal_segments[i][j]);
			if (j > 0) vertical_segments[i][j] = Merge(vertical_segments[i][j - 1], vertical_segments[i][j]);
		}
	}

	long long result = 0;
	for (int i = 1; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			for (auto& x: horizontal_segments[i - 1][j]) {
				for (auto& y: vertical_segments[i][j - 1]) {
					if (x.first <= y.second && y.first <= x.second)
						++result;
				}
			}
		}
	}

	/* for (int i = 1; i < n; ++i) {
		for (int j = 1; j < m; ++j) {
			cout << i << ' ' << j << ": " << endl;
			cout << "HORIZONTAL: "; for (auto& x: horizontal_segments[i - 1][j]) cout << x.first << ' '; cout << endl;
			cout << "VERTICAL: "; for (auto& x: vertical_segments[i][j - 1]) cout << x.first << ' '; cout << endl;
		}
	} */

	return result;
}

• 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: 0 / 28