Submission #1067951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067951		Gromp15	Rectangles (IOI19_rect)	C++17	37 / 100	438 ms	1048576 KiB

rect

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include "rect.h"
#define ll long long
#define ar array
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)

long long count_rectangles(std::vector<std::vector<int>> a) {
	int n = sz(a), m = sz(a[0]);
	vector ok(n, vector(n, vector<int>(m)));
	for (int i = 0; i < m; i++) {
		for (int j = 1; j < n-1; j++) {
			int mx = 0;
			for (int k = j; k < n-1; k++) {
				ckmax(mx, a[k][i]);
				ok[j][k][i] = (mx >= min(a[j-1][i], a[k+1][i])) + (i ? ok[j][k][i-1] : 0);
			}
		}
	}
	vector ok2(m, vector(m, vector<int>(n)));
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < m-1; j++) {
			int mx = 0;
			for (int k = j; k < m-1; k++) {
				ckmax(mx, a[i][k]);
				ok2[j][k][i] = (mx >= min(a[i][j-1], a[i][k+1])) + (i ? ok2[j][k][i-1] : 0);
			}
		}
	}
	long long ans = 0;
	for (int i = 1; i < n-1; i++) for (int j = i; j < n-1; j++) {
		for (int k = 1; k < m-1; k++) {
			int l = min(m-2, int(upper_bound(all(ok[i][j]), ok[i][j][k-1]) - ok[i][j].begin() - 1));
			if (l < k) continue;
			for (int t = k; t <= l; t++) {
				ans += !(ok[i][j][t] - ok[i][j][k-1]) && !(ok2[k][t][j] - ok2[k][t][i-1]);
			}
		}
	}
	return ans;
}

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