Submission #1290769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290769		lucasdmy	Rectangles (IOI19_rect)	C++20	Compilation error	0 ms	0 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN=2510;
vector<int>u(MAXN*MAXN, MAXN), d(MAXN*MAXN), l(MAXN*MAXN, MAXN), r(MAXN*MAXN);
vector<bool>ok(MAXN*MAXN, true);
vector<int>dx{0, 0, 1, -1}, dy{1, -1, 0, 0};
int marc[MAXN][MAXN];
void dfs(int x, int y, int c, int n, int m){
    if(x==0 or x==n or y==0 or y==m){
        ok[c]=false;
        return;
    }
    marc[x][y]=1;
    l[c]=min(l[c], y);
    r[c]=max(r[c], y);
    u[c]=min(u[c], x);
    d[c]=max(d[c], x);
    for(int k=0;k<4;k++){
        if(marc[x+dx[k]][y+dy[k]]==0){
            dfs(x+dx[k], y+dy[k], c, n, m);
        }
    }
}
long long int count_rectangles(vector<vector<int>>v){
    int n=v.size(), m=v[0].size();
    if(n<3 or m<3){
        return 0;
    }
    long long int resp=0;
    for(int k=0;k<n;k++){
	    for(int i=0;i<m;i++){
	        marc[k][i]=v[k][i];
	    }
	}
	int comp=0;
	for(int k=1;k<n-1;k++){
	    for(int i=1;i<m-1;i++){
	        if(marc[k][i]==0){
	            comp++;
	            dfs(k, i, comp, n, m);
	        }
	    }
	}
    int parsum[n][m];
	for(int k=0;k<n;k++){
	    for(int i=0;i<m;i++){
	        if(k==0){
	            if(i==0){
	                parsum[k][i]=v[k][i];
	            }else{
	                parsum[k][i]=v[k][i]+parsum[k][i-1];
	            }
	        }else if(i==0){
	            parsum[k][i]=v[k][i]+parsum[k-1][i];
	        }else{
	            parsum[k][i]=v[k][i]+parsum[k-1][i]+parsum[k][i-1]-parsum[k-1][i-1];
	        }
	    }
	}
	for(int k=1;k<=comp;k++){
	    int up=u[k], down=d[k], left=l[k], right=r[k];
	    if(parsum[down][right]-parsum[up-1][right]-parsum[down][left-1]+parsum[up-1][left-1]==0){
	        if(ok[k]){
	            resp++;
	        }
	    }
	}
	return resp;
}
/*int main()
{
    int n, m;
    cin>>n>>m;
    vector<vector<int>>v(n, vector<int>(m));
    for(int k=0;k<n;k++){
        for(int i=0;i<m;i++){
            cin>>v[k][i];
        }
    }
    cout<<count_rectangles(v);
    return 0;
}*/