Submission #299110

#	Time	Username	Problem	Language	Result	Execution time	Memory
299110		TMJN	Rectangles (IOI19_rect)	C++17	0 / 100	5035 ms	384 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
int S[2500][2500];
int H,W,res;
 
int calc(int lx,int rx,int ly,int ry){
	return S[rx][ry]-(ly?S[rx][ly-1]:0)-(lx?S[lx-1][ry]:0)+((lx&&ly)?S[lx-1][ly-1]:0);
}

long long count_rectangles(vector<vector<int>>a){
	H=a.size();
	W=a[0].size();
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			S[i][j]+=a[i][j];
		}
	}
	for(int i=0;i<H;i++){
		for(int j=1;j<W;j++){
			S[i][j]+=S[i][j-1];
		}
	}
	for(int i=0;i<W;i++){
		for(int j=1;j<H;j++){
			S[j][i]+=S[j-1][i];
		}
	}
	for(int i=1;i<H-1;i++){
		for(int j=1;j<W-1;j++){
			if(a[i-1][j]&&a[i][j-1]&&a[i][j]){
				int xr,yr;
				for(yr=j;yr<W-1&&!a[i][yr];yr++);
				yr--;
				for(xr=i;xr<H-1&&!a[xr][j];xr++);
				xr--;
				if(calc(i,xr,j,yr)==0&&calc(i,xr,j-1,j-1)==xr-i+1&&calc(i,xr,yr+1,yr+1)==xr-i+1&&calc(i-1,i-1,j,yr)==yr-j+1&&calc(xr+1,xr+1,j,yr)==yr-j+1)res++;				
				j=yr;
			}
		}
	}
	return res;
}

• 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