Submission #986977

#	Time	Username	Problem	Language	Result	Execution time	Memory
986977		PagodePaiva	Rectangles (IOI19_rect)	C++17	0 / 100	105 ms	54664 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>

using namespace std;

const int N = 2510;

int n, m;
int v[N][N];
// int linha[N][N][N], coluna[N][N][N]; 
int mark[N][N];
int lmax[N], lmin[N], rmax[N], rmin[N], qtd[N];

void dfs(int i, int j, int con){
	mark[i][j] = con;
	// cout << i << ' ' << j << ' ' << con << '\n';
	qtd[con]++;
	lmax[con] = max(lmax[con], i);
	lmin[con] = min(lmin[con], i);
	rmax[con] = max(rmax[con], j);
	rmin[con] = min(rmin[con], j);
	if(i > 1 and v[i-1][j] == 0 and mark[i-1][j] == 0) dfs(i-1, j, con);
	if(i < n and v[i+1][j] == 0 and mark[i+1][j] == 0) dfs(i+1, j, con);
	if(j > 1 and v[i][j-1] == 0 and mark[i][j-1] == 0) dfs(i, j-1, con);
	if(j < m and v[i][j+1] == 0 and mark[i][j+1] == 0) dfs(i, j+1, con);
	return;
}

int markcon[N];

long long count_rectangles(std::vector<std::vector<int> > a) {
	n = a.size();
	m = a[0].size();
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			v[i+1][j+1] = a[i][j];
		}
	}
	int con = 1;
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			if(mark[i][j] == 0 and v[i][j] == 0) {
				lmax[con] = i; lmin[con] = i;
				rmax[con] = j; rmin[con] = j;
				dfs(i, j, con);
				con++;
			}
		}
	}
	int res = 0;
	for(int i = 2;i < n;i++){
		for(int j = 2;j < m;j++){
			if(v[i][j] == 1) continue;
			if(markcon[mark[i][j]] == 0){
				markcon[mark[i][j]] = 1;
				con = mark[i][j];
				// cout << mark[i][j] << ' '; 
				// cout << lmax[con] << ' ' << lmin[con] << ' ' << rmax[con] << ' ' << rmin[con] << ' ' << qtd[con] << '\n';
				if(qtd[con] == (lmax[con]-lmin[con]+1)*(rmax[con]-rmin[con]+1) and lmax[con] < n and lmin[con] > 0 and rmax[con] < m and rmin[con] > 0) res++;
			}
		}
	}
	return res;
	// for(int l = 1;l <= n;l++){
	// 	for(int i = 1;i <= m;i++){
	// 		linha[l][i][i] = v[l][i];
	// 		for(int j = i+1;j <= m;j++){
	// 			linha[l][i][j] = max(linha[l][i][j-1], v[l][j]);
	// 		}
	// 	}
	// }
	// for(int c = 1;c <= m;c++){
	// 	for(int i = 1;i <= n;i++){
	// 		coluna[c][i][i] = v[i][c];
	// 		for(int j = i+1;j <= m;j++){
	// 			coluna[c][i][j] = max(coluna[c][i][j-1], v[j][c]);
	// 		}
	// 	}
	// }
	// int res = 0;
	// for(int l1 = 2;l2 < n;l2++){
	// 	for(int r1 = 2;r1 < n;r1++){

	// 	}
	// }	
}

• 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