Submission #579447

#	Time	Username	Problem	Language	Result	Execution time	Memory
579447		djs100201	Rectangles (IOI19_rect)	C++17	25 / 100	1085 ms	785576 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;
short R[n_][n_], U[n_][n_], D[n_][n_], L[n_][n_];
vector<short>row[n_][n_], idx[n_][n_];
short tree_[n_];
int f(int l, int r) {
	r++;
	int ret = 0;
	for (; l; l -= (l & -l))ret -= tree_[l];
	for (; r; r -= (r & -r))ret += tree_[r];
	return ret;
}
void update(int i, int val) {
	i++;
	for (; i <= max(n, m); i += i & -i)tree_[i] += val;
}
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 });
			while (B.size() && B.top().first <= arr[i][m - 1 - j])B.pop();
			if (B.empty())R[i][m - 1 - j] = -1;
			else R[i][m - 1 - j] = B.top().second;
			B.push({ arr[i][m - 1 - j],m - 1 - 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 });
			while (B.size() && B.top().first <= arr[n - 1 - j][i])B.pop();
			if (B.empty())D[n - 1 - j][i] = -1;
			else D[n - 1 - j][i] = B.top().second;
			B.push({ arr[n - 1 - j][i],n - 1 - j });
		}
	}
	vector<vector<short>>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)continue;
			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++) {
			for (auto nxt : row[i][j])update(nxt, 1);
			for (auto nxt : idx[i][j]) {
				ll l = query[nxt][0], r = query[nxt][1];
				int len = f(l + 1, r - 1);
				if (len == r - l - 1)now[nxt]++;
			}
			for (auto nxt : row[i][j])update(nxt, -1);
			row[i][j].clear();
			idx[i][j].clear();
		}
	cnt = 0;
	for (auto nxt : query) {
		if (now[cnt] == 0) {
			cnt++;
			continue;
		}
		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)continue;
			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++) {
			for (auto nxt : row[i][j])update(nxt, 1);
			for (auto nxt : idx[i][j]) {
				ll l = query[nxt][2], r = query[nxt][3];
				int len = f(l + 1, r - 1);
				if (len == r - l - 1)ret++;
			}
			for (auto nxt : row[i][j])update(nxt, -1);
		}
	return ret;
}

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