Submission #1196397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196397		stdfloat	Rectangles (IOI19_rect)	C++20	72 / 100	5099 ms	686244 KiB

rect

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

using ll = long long;

ll count_rectangles(vector<vector<int>> a) {
	int n = (int)a.size(), m = (int)a[0].size();

	vector<vector<int>> L(n, vector<int>(m)), R = L, U = L, D = L;
	for (int i = 0; i < n; i++) {
		stack<int> s;
		for (int j = 0; j < m; j++) {
			while (!s.empty() && a[i][s.top()] < a[i][j]) s.pop();
		
			L[i][j] = (s.empty() ? 0 : s.top());
			s.push(j);
		}

		while (!s.empty()) s.pop();

		for (int j = m - 1; j >= 0; j--) {
			while (!s.empty() && a[i][j] > a[i][s.top()]) s.pop();

			R[i][j] = (s.empty() ? m - 1 : s.top());
			s.push(j);
		}
	}
	for (int i = 0; i < m; i++) {
		stack<int> s;
		for (int j = 0; j < n; j++) {
			while (!s.empty() && a[s.top()][i] < a[j][i]) s.pop();

			U[j][i] = (s.empty() ? 0 : s.top());
			s.push(j);
		}

		while(!s.empty()) s.pop();

		for (int j = n - 1; j >= 0; j--) {
			while (!s.empty() && a[j][i] > a[s.top()][i]) s.pop();

			D[j][i] = (s.empty() ? n - 1 : s.top());
			s.push(j);
		}
	}

	vector<vector<vector<int>>> sp(m, vector<vector<int>>(n, vector<int>(13)));
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++)
			sp[i][j][0] = L[j][i];

		for (int j = 1; j < 13; j++) {
			for (int k = 0; k + (1 << j) <= n; k++)
				sp[i][k][j] = max(sp[i][k][j - 1], sp[i][k + (1 << (j - 1))][j - 1]);
		}
	}

	vector<int> lg(n + 1);
	for (int i = 2; i <= n; i++)
		lg[i] = lg[i >> 1] + 1;

	ll cnt = 0;
	for (int i = 1; i < n - 1; i++) {
		for (int j = 1; j < m - 1; j++) {
			int mn = INT_MAX;
			for (int k = i; k < D[i - 1][j] && j < R[k][j - 1]; k++) {
				mn = min(mn, R[k][j - 1]);

				for (int l = j; l < mn && k < D[i - 1][l] && U[k + 1][l] < i; l++) {
					int y = lg[k - i + 1];
					cnt += max(sp[l + 1][i][y], sp[l + 1][k - (1 << y) + 1][y]) < j;

					// bool tr = true;
					// for (int m = i; m <= k && tr; m++)
					// 	tr = (L[m][l + 1] < j);

					// cnt += tr;
				}
			}
		}
	}

	return cnt;
}

• 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