Submission #737138

#	Time	Username	Problem	Language	Result	Execution time	Memory
737138		NeroZein	Rectangles (IOI19_rect)	C++17	0 / 100	1 ms	596 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 p[M], sz[M]; 
int x[M], xx[M], y[M], yy[M];
int pref[N][N]; 

int get (int i, int j) {
	return i * m + j; 
}

int getSum (int i, int ii, int j, int jj) {
	return pref[ii][jj] - pref[i - 1][jj] - pref[ii][j - 1] + pref[i - 1][j - 1];
}

int get (int v) {
	return p[v] = (p[v] == v ? v : get(p[v]));
}

inline void unite (int u, int v) {
	u = get(u); v = get(v);
	if (u == v) return; 
	if (sz[u] < sz[v]) swap(u, v); 
	sz[v] += sz[u]; 
	p[u] = v; 
	x[v] = min(x[v], x[u]); 
	xx[v] = max(xx[v], xx[u]); 
	y[v] = min(y[v], y[u]);
	yy[v] = max(yy[v], yy[u]); 
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	n = (int) a.size(); 
	m = (int) a[0].size(); 
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			int num = get(i, j); 
			p[num] = num;
			sz[num] = 1; 
			x[num] = xx[num] = i;
			y[num] = yy[num] = j;  
			pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1]; 
		}
	}
	for (int i = 1; i < n - 1; ++i) {
		for (int j = 1; j < m - 1; ++j) {
			if (a[i][j] == 0) {
				for (int k = 0; k < 4; ++k) {
					int ni = i + di[k], nj = j + dj[k];
					if (a[ni][nj] == 0) {
						unite(get(i, j), get(ni, nj)); 						
					}
				}
			}
		}
	}
	int ans = 0; 
	for (int i = 1; i < n - 1; ++i) {
		for (int j = 1; j < m - 1; ++j) {
			int num = get(i, j); 
			if (get(num) == num) {
				if (x[num] > 0 && xx[num] < n - 1 && y[num] > 0 && yy[num] < m - 1) {
					ans += getSum(x[num], xx[num], y[num], yy[num]) == 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: 0 / 13
• Subtask 7: 0 / 28