Submission #302624

#	Time	Username	Problem	Language	Result	Execution time	Memory
302624		wilwxk	Rectangles (IOI19_rect)	C++17	0 / 100	17 ms	21504 KiB

rect

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

const int MAXN = 2505;
vector<vector<int> > input;
int seg[4][MAXN][MAXN*4];
int mx[4][MAXN][MAXN];
int n, m;

void build(int k, int id, int sind, int ini, int fim) {
	// printf("build %d %d %d %d %d\n", k, id, sind, ini, fim);
	if (ini == fim) {
		if (k&1) seg[k][id][sind] = mx[k][id][ini];
		else seg[k][id][sind] = mx[k][ini][id];
		// printf("bloh 3\n");
		return;
	}
	int mid = (ini+fim)/2;
	int e = sind*2;
	int d = e+1;
	build(k, id, e, ini, mid);
	// printf("bloh 1\n");
	build(k, id, d, mid+1, fim);
	// printf("bloh 2\n");
	if (k == 0 || k == 2) seg[k][id][sind] = min(seg[k][id][e], seg[k][id][d]);
	else seg[k][id][sind] = max(seg[k][id][e], seg[k][id][d]);
}

int query(int k, int id, int sind, int l, int r, int ql, int qr) {
	if (ql > r || qr < l) return (k == 0 || k == 2) ? MAXN : -1;
	if (ql <= l && qr >= r) return seg[k][id][sind];
	int mid = (l+r)/2;
	int e = sind*2;
	int d = e+1;
	if (k == 0 || k == 2) return min(query(k, id, e, l, mid, ql, qr), query(k, id, d, mid+1, r, ql, qr));
	else return max(query(k, id, e, l, mid, ql, qr), query(k, id, d, mid+1, r, ql, qr));
}

void precalc() {
	stack<int> st;
	// ------------->
	for (int i = 0; i < n; i++) {
		stack<int> st;
		st.push(m);
		for (int j = m; j >= 0; j--) {
			while (st.top() != m && input[i][st.top()] <= input[i][j]) st.pop();
			mx[0][i+1][j+1] = (st.top()-1)+1;
			st.push(j);
		}
	}
	// ^^^^^^^^^^^^^
	while (st.size()) st.pop();
	for (int j = 0; j < m; j++) {
		stack<int> st;
		st.push(-1);
		for (int i = 0; i < n; i++) {
			while (st.top() != -1 && input[st.top()][j] < input[i][j]) st.pop();
			mx[1][i+1][j+1] = (st.top()+1)+1;
			st.push(i);
		}
	}
	// <------------
	while (st.size()) st.pop();
	for (int i = 0; i < n; i++) {
		st.push(-1);
		for (int j = 0; j < m; j++) {
			while (st.top() != -1 && input[i][st.top()] < input[i][j]) st.pop();
			mx[2][i+1][j+1] = (st.top()+1)+1;
			st.push(j);
		}
	}
	// vvvvvvvvvvvv
	while (st.size()) st.pop();
	for (int j = 0; j < m; j++) {
		stack<int> st;
		st.push(n);
		for (int i = n-1; i >= 0; i--) {
			while (st.top() != n && input[st.top()][j] < input[i][j]) st.pop();
			mx[3][i+1][j+1] = (st.top()-1)+1;
			st.push(i);
		}
	}

	for (int k = 0; k < 4; k++) {
		// printf("---k = %d---\n", k);
		for (int i = 1; i <= n; i++) {
			// for (int j = 1; j <= m; j++) printf("%d ", mx[k][i][j]);
			// cout << endl;
		}

		for (int i = 1; i <= n; i++) {
			build(1, i, 1, 1, m);
			// printf("bleh\n");
			build(3, i, 1, 1, m);
		}
			// printf("bleh2\n");
		for (int i = 1; i <= m; i++) {
			build(0, i, 1, 1, n);
			build(2, i, 1, 1, n);
		}
	}

}

bool check(int a, int b, int c, int d) {
	if (a == m || b == 1 || c == 1 || d == n) return 0;
	// printf("check %d %d %d %d\n", a, b, c, d);
	// >>>>>>>>>>>>
	int aa = query(0, c-1, 1, 1, n, b, d);
	// ^^^^^^^^^^^^
	int bb = query(1, d+1, 1, 1, m, c, a);
	// <<<<<<<<<<<<
	int cc = query(2, a+1, 1, 1, n, b, d);
	// vvvvvvvvvvvv
	int dd = query(3, b-1, 1, 1, m, c, a);
	// printf("// %d %d %d %d\n", aa, bb, cc, dd);
	if (aa < a) return 0;
	if (bb > b) return 0;
	if (cc > c) return 0;
	if (dd < d) return 0;
	// printf("good %d %d %d %d\n", a, b, c, d);
	return 1;
}

long long count_rectangles(vector<vector<int> > INPUT) {
	n = INPUT.size();
	m = INPUT[0].size();
	input = INPUT;

	precalc();

	vector<tuple<int, int, int, int> > possi;
	for (int i = 2; i < n; i++) {
		for (int j = 2; j < m; j++) {
			int a = mx[0][i][j];
			int b = mx[1][i][j];
			int c = mx[2][i][j];
			int d = mx[3][i][j];
			possi.push_back({a, b, c, d});
		}
	}
	sort(possi.begin(), possi.end());
	auto it = unique(possi.begin(), possi.end());
	possi.resize(it-possi.begin());

	ll ans = 0;
	for (auto rec : possi) {
		int a, b, c, d;
		tie(a, b, c, d) = rec;
		ans += check(a, b, c, d);
	}

	return ans;
}

• 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