Swimming Pool (2021 NOI Selection Day 1 Problem 3)

swimmingpool.cpp

#include<iostream>
#include<vector> 
#include<set>
#include<algorithm>
#include <assert.h>
using namespace std;
typedef pair<int,int> pi;
typedef vector<int> vi;
#define mp make_pair
#define pb emplace_back
#define f first
#define s second
#define SZ(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound

int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
const int MAXN=2000;
const int MAXL=MAXN*MAXN+MAXN;
int A[MAXN][MAXN];
vector<pi> Q[MAXL];
int R,C;
int ans=0;
pi p[MAXN][MAXN];
pi ht[MAXN][MAXN];
pi lr[MAXN][MAXN];
int sz[MAXN][MAXN];
int open[MAXN][MAXN];
int mem[MAXN][MAXN];
vi des;

pi par(pi a){
	if(p[a.f][a.s].f==a.f&&p[a.f][a.s].s==a.s)return a;
	return p[a.f][a.s]=par(p[a.f][a.s]);
}

pi mrg(pi a, pi b){
	return mp(min(a.f,b.f), max(a.s,b.s));
}

void merge(pi a, pi b){
	if(par(a)==par(b))return;
	// cerr<<"Merging "<<a.f<<' '<<a.s<<" with "<<b.f<<' '<<b.s<<'\n';
	a=par(a);b=par(b);
	if(a==b)return;
	// cerr<<"A ";
	if(sz[a.f]<sz[b.f])swap(a,b); //a is bigger
	ht[a.f][a.s]=mrg(ht[a.f][a.s],ht[b.f][b.s]);
	lr[a.f][a.s]=mrg(lr[a.f][a.s],lr[b.f][b.s]);
	sz[a.f][a.s]=sz[a.f][a.s]+sz[b.f][b.s];
	p[b.f][b.s]=a;
	// cerr<<"Size "<<sz[a.f][a.s]<<'\n';
}

int works(pi x){
	int a=ht[x.f][x.s].s - ht[x.f][x.s].f+1;
	int b=lr[x.f][x.s].s - lr[x.f][x.s].f+1;
	if(ht[x.f][x.s].f==0)return 0;
	if(lr[x.f][x.s].f==0)return 0;
	if(lr[x.f][x.s].s==C-1)return 0;
	if(ht[x.f][x.s].s==R-1)return 0;
	if(a*b == sz[x.f][x.s])return 1;
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>R>>C;
	for(int i=0;i<R;++i)for(int j=0;j<C;++j){
		cin>>A[i][j];
	}
	for(int i=0;i<R;++i)for(int j=0;j<C;++j){
		Q[A[i][j]].pb(mp(i,j));
		p[i][j]=mp(i,j);
		ht[i][j]=mp(i,i);
		lr[i][j]=mp(j,j);
		sz[i][j]=0;
	}
	for(int i=0;i<MAXL;++i)if(SZ(Q[i])){
		vector<pi> alx;
		for(auto t:Q[i]){
			int x=t.f;
			int y=t.s;
			open[x][y]=1;
			assert(sz[x][y]==0);
			sz[x][y]=1;
			for(int t=0;t<4;++t){
				int cx=dx[t]+x;
				int cy=dy[t]+y;
				if(cx<0||cy<0||cx>=R||cy>=C)continue;
				if(!open[cx][cy])continue;
				merge(mp(x,y),mp(cx,cy));
			}
			alx.pb(mp(x,y));
		}
		for(auto i:alx){
			pi a=par(i);
			if(mem[a.f][a.s])continue;
			mem[a.f][a.s]=1;
			if(works(a))++ans;
		}
		for(auto i:alx){
			pi a=par(i);
			mem[a.f][a.s]=0;
		}
	}
	cout<<ans;
}