Submission #579420

#	Time	Username	Problem	Language	Result	Execution time	Memory
579420		djs100201	Rectangles (IOI19_rect)	C++17	0 / 100	1046 ms	421960 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using ll = long long;
using namespace std;
const int n_ = 2505;
using P = pair<int, int>;
ll n, m, k, tc = 1, a, b, c, d, sum, x, y, z, base, ans, q;
int R[n_][n_], U[n_][n_], D[n_][n_], L[n_][n_];
vector<int>row[n_][n_], idx[n_][n_];
long long count_rectangles(std::vector<std::vector<int> > arr) {
	ll ret = 0;
	n = arr.size();
	m = arr[0].size();
	for (int i = 0; i < n; i++) {
		stack<P>A, B;
		A.push({ arr[i][0],0 });
		B.push({ arr[i][m - 1],m - 1 });
		for (int j = 1; j < m; j++) {
			while (A.size() && A.top().first <= arr[i][j])A.pop();
			if (A.empty())L[i][j] = -1;
			else L[i][j] = A.top().second;
			A.push({ arr[i][j],j });
		}
		for (int j = m - 2; j >= 0; j--) {
			while (B.size() && B.top().first <= arr[i][j])B.pop();
			if (B.empty())R[i][j] = -1;
			else R[i][j] = B.top().second;
			B.push({ arr[i][j],j });
		}
	}
	for (int i = 0; i < m; i++) {
		stack<P>A, B;
		A.push({ arr[0][i],0 });
		B.push({ arr[n - 1][i],n - 1 });
		for (int j = 1; j < n; j++) {
			while (A.size() && A.top().first <= arr[j][i])A.pop();
			if (A.empty())U[j][i] = -1;
			else U[j][i] = A.top().second;
			A.push({ arr[j][i],j });
		}
		for (int j = n - 2; j >= 0; j--) {
			while (B.size() && B.top().first <= arr[j][i])B.pop();
			if (B.empty())D[j][i] = -1;
			else D[j][i] = B.top().second;
			B.push({ arr[j][i],j });
		}
	}
	for (int i = 0; i < n; i++)arr[i].clear();
	vector<vector<int>>query;
	for (int j = 1; j + 1 < m; j++)
		for (int i = 1; i + 1 < n; i++) {
			if (D[i][j] != -1 && U[i][j] != -1) {
				if (row[U[i][j]][D[i][j]].size() && row[U[i][j]][D[i][j]].back() == j)continue;
				row[U[i][j]][D[i][j]].push_back(j);
				if (L[i][j] != -1 && R[i][j] != -1) {
					query.push_back({ L[i][j],R[i][j],U[i][j],D[i][j] });
				}
			}
		}
	sort(all(query));
	query.erase(unique(query.begin(), query.end()), query.end());
	int cnt = 0;
	for (auto nxt : query) {
		idx[nxt[2]][nxt[3]].push_back(cnt);
		cnt++;
	}
	assert(cnt <= n * m);
	vector<int>now(cnt + 1);
	for (int i = 0; i < n; i++)
		for (int j = i + 2; j < n; j++) {
			vector<int>t(row[i][j].size());
			x = 0;
			for (auto nxt : row[i][j])t[x++] = nxt;
			for (auto nxt : idx[i][j]) {
				ll l = query[nxt][0], r = query[nxt][1];
				int len = upper_bound(all(t), r - 1) - lower_bound(all(t), l + 1);
				if (len == r - l - 1)now[nxt]++;
			}
		}
	cnt = 0;
	for (auto nxt : query) {
		idx[nxt[0]][nxt[1]].push_back(cnt);
		cnt++;
	}
	for (int i = 1; i + 1 < n; i++)
		for (int j = 1; j + 1 < m; j++) {
			if (L[i][j] != -1 && R[i][j] != -1) {
				if (row[L[i][j]][R[i][j]].size() && row[L[i][j]][R[i][j]].back() == i)continue;
				row[L[i][j]][R[i][j]].push_back(i);
			}
		}
	for (int i = 0; i < m; i++)
		for (int j = i + 2; j < m; j++) {
			vector<int>t(row[i][j].size());
			x = 0;
			for (auto nxt : row[i][j])t[x++] = (nxt);
			for (auto nxt : idx[i][j]) {
				if (now[nxt] == 0)continue;
				ll l = query[nxt][2], r = query[nxt][3];
				int len = upper_bound(all(t), r - 1) - lower_bound(all(t), l + 1);
				if (len == r - l - 1)now[nxt]++;
			}
		}
	for (int i = 0; i < cnt; i++)if (now[i] == 2)ret++;
	return ret;
}

• 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