Submission #171201

#	Time	Username	Problem	Language	Result	Execution time	Memory
171201		nobik	Rectangles (IOI19_rect)	C++14	72 / 100	5105 ms	608712 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;
}

struct Fenwick {
	int n;
	vector<int> f;

	Fenwick(int n): n(n), f(n + 1) {}

	void Add(int pos) {
		for (int i = pos + 1; i <= n; i += i & -i) {
			++f[i];
		}
	}

	int Sum(int pos) {
		int r = 0;
		for (int i = pos + 1; i > 0; i -= i & -i) {
			r += f[i];
		}

		return r;
	}
};

int Count(vector<pair<int, int>> a, vector<pair<int, int>> b) {
	if (a.empty() || b.empty()) return 0;
	sort(a.begin(), a.end(), [&](const pair<int, int>& x, const pair<int, int>& y) {
		return x.second < y.second;
	});

	vector<int> cmp;
	for (auto& e: b) {
		cmp.push_back(e.second);
	}

	sort(cmp.begin(), cmp.end());
	cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());
	Fenwick f(cmp.size());

	int b_size = static_cast<int>(b.size());
	int j = 0;

	int r = 0;
	for (auto& e: a) {
		while (j < b_size && b[j].first <= e.second) {
			int y = lower_bound(cmp.begin(), cmp.end(), b[j].second) - cmp.begin();
			f.Add(y);
			++j;
		}

		int pos = lower_bound(cmp.begin(), cmp.end(), e.first) - cmp.begin() - 1;
		r += j - f.Sum(pos);
	}

	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 = 1; 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;
				}
			} */

			result += Count(horizontal_segments[i - 1][j], vertical_segments[i][j - 1]);
		}
	}

	/* 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