Submission #737201

#	Time	Username	Problem	Language	Result	Execution time	Memory
737201		NeroZein	Rectangles (IOI19_rect)	C++17	13 / 100	455 ms	485232 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std; 
 
const int N = 2503;
const int M = N * N;
 
const int di[] = {0, 0, 1, -1}; 
const int dj[] = {1, -1, 0, 0};
 
int n, m; 
int ncc; 
int vis[N][N];
int pref[N][N]; 
vector<vector<int>> a; 
 
void Dfs (int x, int y) {
	vis[x][y] = ncc;
	for (int i = 0; i < 4; ++i) {
		int nx = x + di[i];
		int ny = y + dj[i];
		if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
			continue; 
		}
		if (vis[nx][ny]) {
			continue; 
		}
		if (a[nx][ny] == 1) {
			continue; 
		}
		Dfs(nx, ny); 
	}
}
 
int mnX[M], mxX[M], mnY[M], mxY[M]; 
 
long long count_rectangles(std::vector<std::vector<int> > A) {
	n = (int) A.size(); 
	m = (int) A[0].size(); 
	a = A; 
	for (int i = 1; i < n - 1; ++i) {
		for (int j = 1; j < m - 1; ++j) {
			if (!vis[i][j] && a[i][j] == 0) {
				ncc++;
				Dfs(i, j); 
			}
		}
	}
	fill(mnX + 1, mnX + ncc + 1, N); 
	fill(mnY + 1, mnY + ncc + 1, N);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			mnX[vis[i][j]] = min(mnX[vis[i][j]], i); 
			mnY[vis[i][j]] = min(mnY[vis[i][j]], j); 
			mxX[vis[i][j]] = max(mxX[vis[i][j]], i); 
			mxY[vis[i][j]] = max(mxY[vis[i][j]], j); 
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			pref[i][j] = a[i][j]; 
			if (i - 1 >= 0) {
				pref[i][j] += pref[i - 1][j]; 
			}
			if (j - 1 >= 0) {
				pref[i][j] += pref[i][j - 1];
			}
			if (i - 1 >= 0 && j - 1 >= 0) {
				pref[i][j] -= pref[i - 1][j - 1]; 
			}
		}
	}
	auto qry = [&](int x, int y, int xx, int yy) {
		return pref[xx][yy] - pref[xx][y - 1] - pref[x - 1][yy] + pref[x - 1][y - 1]; 
	};
	int ans = 0;  
	for (int i = 1; i <= ncc; ++i) {
		if (mnX[i] > 0 && mxX[i] < n - 1 && mnY[i] > 0 && mxY[i] < m - 1) {
			ans += qry(mnX[i], mnY[i], mxX[i], mxY[i]) == 0; 
		}
	}
	return ans; 
}

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