Submission #380014

#	Time	Username	Problem	Language	Result	Execution time	Memory
380014		SuhaibSawalha1	Rectangles (IOI19_rect)	C++17	38 / 100	5056 ms	639364 KiB

rect

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

vector<int> lg{-1};

struct RMQ {
	vector<vector<int>> sp;
	void init (vector<int> &a) {
		int n = a.size();
		sp.resize(lg[n]+1, vector<int>(n));
		sp[0] = a;
		for (int i = 1; i < lg[n]+1; ++i) {
			for (int j = 0; j < n - (1 << i) + 1; ++j) {
				sp[i][j] = max(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
			}
		}
	}
	int query (int l, int r) {
		assert(r >= l);
		int k = lg[r-l+1];
		return max(sp[k][l], sp[k][r - (1 << k) + 1]);
	}
};

long long count_rectangles(vector<vector<int>> a) {
	int n = a.size(), m = a[0].size();
	if (n <= 3) {
		int n = a.size(), m = a[0].size();
		long long ans = 0;
		for (int x = 1; x < n - 1; ++x) {
			for (int y = 1; y < m - 1; ++y) {
				for (int i = x; i < n  - 1; ++i) {
					if (a[i][y] >= a[i][y - 1]) {
						break;
					}
					for (int j = y; j < m - 1; ++j) {
						bool good = 1, bad = 0;
						for (int l = x; l <= i && !bad; ++l) {
							for (int r = y; r <= j && !bad; ++r) {
								good &= a[l][r] < a[l][j + 1] && a[l][r] < a[i + 1][r];
								bad |= a[l][r] >= a[l][y - 1] || a[l][r] >= a[x - 1][r];
							}
						}
						if (bad) {
							break;
						}
						ans += good;
					}
				}
			}
		}
		return ans;
	}
	for (int i = 1; i <= max(n, m); ++i) {
		lg.push_back(lg.back()+!(i&(i-1)));
	}
	vector<RMQ> row(n), col(m);
	for (int i = 0; i < n; ++i) {
		row[i].init(a[i]);
	}
	for (int j = 0; j < m; ++j) {
		vector<int> p;
		for (int i = 0; i < n; ++i) {
			p.push_back(a[i][j]);
		}
		col[j].init(p);
	}
	long long ans = 0;
	for (int x = 1; x < n - 1; ++x) {
		for (int y = 1; y < m - 1; ++y) {
			for (int i = x; i < n  - 1; ++i) {
				if (a[i][y] >= a[i][y - 1] || a[i][y] >= a[x - 1][y]) {
					break;
				}
				for (int j = y; j < m - 1; ++j) {
					bool good = 1, bad = 0;
					for (int l = x; l <= i && !bad; ++l) {
						int mx = row[l].query(y, j);
						good &= mx < a[l][j + 1];
						bad |= mx >= a[l][y - 1];
					}
					for (int r = y; r <= j && !bad; ++r) {
						int mx = col[r].query(x, i);
						good &= mx < a[i + 1][r];
						bad |= mx >= a[x - 1][r];
					}
					if (bad) {
						break;
					}
					ans += good;
				}
			}
		}
	}
	return ans;
}

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