Submission #1210548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210548		bangan	Rectangles (IOI19_rect)	C++20	13 / 100	257 ms	123120 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 2500 + 4;

int pre[N][N];
int r[N][N];
int d[N][N];

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

long long count_rectangles(std::vector<std::vector<int>> a) {
	memset(r, -1, sizeof r);
	memset(d, -1, sizeof d);
	int n = a.size();
	int m = a[0].size();
	for (int i=0; i<n; i++) for (int j=0; j<m; j++) pre[i+1][j+1] = a[i][j] + pre[i+1][j] + pre[i][j+1] - pre[i][j];
	for (int i=1; i+1<n; i++) for (int j=m-2; j>=1; j--) if (!a[i][j]) {
		if (j==m-2 || a[i][j+1]==1) r[i][j]=j;
		else r[i][j] = r[i][j+1];
	}
	for (int j=1; j+1<m; j++) for (int i=n-2; i>=1; i--) if (!a[i][j]) {
		if (i==n-2 || a[i+1][j]==1) d[i][j]=i;
		else d[i][j] = d[i+1][j];
	}
	int ans=0;
	for (int i=1; i+1<n; i++) for (int j=1; j+1<m; j++) if (!a[i][j]) {
		int ii=d[i][j];
		int jj=r[i][j];
		ans += get(i,j,ii,jj)==0 && get(i-1,j,i-1,jj)==jj-j+1 && get(ii+1,j,ii+1,jj)==jj-j+1 && get(i,j-1,ii,j-1)==ii-i+1 && get(i,jj+1,ii,jj+1)==ii-i+1;
	} 
	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