Submission #197757

#	Time	Username	Problem	Language	Result	Execution time	Memory
197757		Minnakhmetov	Rectangles (IOI19_rect)	C++14	72 / 100	5045 ms	514860 KiB

rect

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

#define ll long long

const int N = 2505;
int stk[N], to_l[N], to_r[N], w[N], last_v[N][N], last_h[N][N], c_v[N][N], c_h[N][N];
vector<int> lt[N][N], up[N][N];

void handle(int len) {
	fill(to_l, to_l + len, -1);
	fill(to_r, to_r + len, -1);

	int z = 0;

	for (int i = 0; i < len; i++) {
		while (z > 0 && w[stk[z - 1]] <= w[i]) {
			to_r[stk[--z]] = i;
		}
		stk[z++] = i;
	}

	z = 0;

	for (int i = len - 1; i >= 0; i--) {
		while (z > 0 && w[stk[z - 1]] <= w[i]) {
			to_l[stk[--z]] = i;
		}
		stk[z++] = i;
	}
}

ll count_rectangles(vector<vector<int>> a) {
	// w[0] = 1;
	// w[1] = 0;
	// w[2] = 1;

	// handle(3);

	// for (int i = 0; i < 3; i++) {
	// 	cout << to_l[i] << " ";
	// }
	// cout << "\n";
	// for (int i = 0; i < 3; i++) {
	// 	cout << to_r[i] << " ";
	// }
	// cout << "\n";

	// return 0;

	int n = a.size(),
		m = a[0].size();

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			w[j] = a[i][j];
		handle(m);
		for (int j = 0; j < m; j++) {
			if (to_l[j] != -1 && to_l[j] + 1 < j) {
				lt[i][j - 1].push_back(to_l[j] + 1);
			}
			if (to_r[j] != -1 && to_l[to_r[j]] != j && j + 1 < to_r[j]) {
				lt[i][to_r[j] - 1].push_back(j + 1);
			}
		}
	}

	for (int j = 0; j < m; j++) {
		for (int i = 0; i < n; i++) {
			w[i] = a[i][j];
		}
		handle(n);
		for (int i = 0; i < n; i++) {
			if (to_l[i] != -1 && to_l[i] + 1 < i) {
				up[i - 1][j].push_back(to_l[i] + 1);
			}
			if (to_r[i] != -1 && to_l[to_r[i]] != i && i + 1 < to_r[i]) {
				up[to_r[i] - 1][j].push_back(i + 1);
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			last_v[i][j] = -1;
			last_h[i][j] = -1;
		}
	}

	ll ans = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int x : lt[i][j]) {
				if (last_v[j][x] != i - 1)
					c_v[j][x] = 0;
				last_v[j][x] = i;
				c_v[j][x]++;
			}
			for (int x : up[i][j]) {
				if (last_h[i][x] != j - 1)
					c_h[i][x] = 0;
				last_h[i][x] = j;
				c_h[i][x]++;

				for (int y : lt[i][j]) {
					if (i - c_v[j][y] + 1 <= x && j - c_h[i][x] + 1 <= y)
						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: 13 / 13
• Subtask 7: 0 / 28