Submission #830539

#	Time	Username	Problem	Language	Result	Execution time	Memory
830539		pavement	Rectangles (IOI19_rect)	C++17	59 / 100	5029 ms	173812 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define eb emplace_back

using ii = pair<int, int>;
using ll = long long;

ll count_rectangles(vector<vector<int> > a) {
	ll ans = 0;
	int n = (int)a.size(), m = (int)a[0].size();
	vector<vector<vector<ii> > > horiz(n, vector<vector<ii> >(m)), vert(n, vector<vector<ii> >(m));
	for (int i = 1; i + 1 < n; i++) {
		for (int j = 1; j + 1 < m; j++) {
			for (int k = j, r = 0; k >= 1; k--) {
				r = max(r, a[i][k]);
				if (r < min(a[i][j + 1], a[i][k - 1])) horiz[i][j].eb(k, 1);
			}
		}
	}
	for (int j = 1; j + 1 < m; j++) {
		for (int i = 1; i + 1 < n; i++) {
			for (int k = i, r = 0; k >= 1; k--) {
				r = max(r, a[k][j]);
				if (r < min(a[i + 1][j], a[k - 1][j])) vert[i][j].eb(k, 1);
			}
		}
	}
	for (int i = 1; i + 1 < n; i++) {
		for (int j = 1; j + 1 < m; j++) {
			reverse(horiz[i][j].begin(), horiz[i][j].end());
			reverse(vert[i][j].begin(), vert[i][j].end());
			for (auto &[k, l] : horiz[i][j]) {
				auto it = lower_bound(horiz[i - 1][j].begin(), horiz[i - 1][j].end(), mp(k, 0));
				if (it != horiz[i - 1][j].end() && it->first == k) {
					l = it->second + 1;
				}
			}
			for (auto &[k, l] : vert[i][j]) {
				auto it = lower_bound(vert[i][j - 1].begin(), vert[i][j - 1].end(), mp(k, 0));
				if (it != vert[i][j - 1].end() && it->first == k) {
					l = it->second + 1;
				}
			}
			for (auto [k1, l1] : horiz[i][j]) {
				for (auto [k2, l2] : vert[i][j]) {
					int width = j - k1 + 1, height = i - k2 + 1;
					if (width <= l2 && height <= l1) {
						ans++;
					}
				}
			}
		}
	}
	return ans;
}

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