Submission #579412

#	Time	Username	Problem	Language	Result	Execution time	Memory
579412		djs100201	Rectangles (IOI19_rect)	C++17	72 / 100	2541 ms	1048576 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;
vector<vector<int>>R, L, U, D;
vector<int>row[n_][n_], col[n_][n_], idx[n_][n_], idx2[n_][n_];
long long count_rectangles(std::vector<std::vector<int> > arr) {
	/*
	6 5
	4 8 7 5 6
	7 4 10 3 5
	9 7 20 14 2
	9 14 7 3 6
	5 7 5 2 7
	4 5 13 5 6
	*/
	ll ret = 0;
	n = arr.size();
	m = arr[0].size();
	R.resize(n + 1), L.resize(n + 1), U.resize(n + 1), D.resize(n + 1);
	for (int i = 0; i <= n; i++) {
		R[i].resize(m + 1);
		L[i].resize(m + 1);
		U[i].resize(m + 1);
		D[i].resize(m + 1);
	}
	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 i = 1; i + 1 < n; i++)
		for (int j = 1; j + 1 < m; j++) {
			if(U[i][j]!=-1 && D[i][j]!=-1)row[U[i][j]][D[i][j]].push_back(j);
			if (L[i][j] != -1 && R[i][j] != -1) {
				if (col[L[i][j]][R[i][j]].size() && col[L[i][j]][R[i][j]].back() == i)continue;
				col[L[i][j]][R[i][j]].push_back(i);
			}
			if (D[i][j] != -1 && U[i][j] != -1 && L[i][j] != -1 && R[i][j] != -1)query.push_back({ L[i][j],R[i][j],U[i][j],D[i][j] });
		}
	for (int i = 0; i <= n; i++) {
		R[i].clear();
		L[i].clear();
		U[i].clear();
		D[i].clear();
	}
	sort(all(query));
	query.erase(unique(query.begin(), query.end()), query.end());
	int cnt = 0;
	for (auto nxt : query) {
		idx[nxt[0]][nxt[1]].push_back(cnt);
		idx2[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;
			row[i][j].clear();
			sort(all(t));
			t.erase(unique(t.begin(), t.end()), t.end());
			for (auto nxt : idx2[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]++;
			}
		}
	for (int i = 0; i < m; i++)
		for (int j = i + 2; j < m; j++) {
			vector<int>t(col[i][j].size());
			x = 0;
			for (auto nxt : col[i][j])t[x++] = (nxt);
			col[i][j].clear();
			for (auto nxt : idx[i][j]) {
				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: 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