Submission #384297

#	Time	Username	Problem	Language	Result	Execution time	Memory
384297		kshitij_sodani	Rectangles (IOI19_rect)	C++14	72 / 100	5089 ms	726860 KiB

rect

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n' 


#include "rect.h"
vector<vector<int>> it;
int n,m;

int le[2501][2501];
int re[2501][2501];
int uu[2501][2501];
int dd[2501][2501];
vector<pair<int,int>> pre[2501][2501];

vector<int> x={1,-1,0,0};
vector<int> y={0,0,-1,1};
int vis[2501][2501];

vector<pair<int,int>> comp;
void dfs(int i,int j){
	vis[i][j]=1;
	comp.pb({i,j});
	//<<i<<",,"<<j<<endl;
	for(int ii=0;ii<4;ii++){
		int xx=i+x[ii];
		int yy=j+y[ii];
		if(xx<0 or yy<0 or xx>=n or yy>=m){
			continue;
		}
		if(it[xx][yy]==0){
			if(vis[xx][yy]==0){
				dfs(xx,yy);
			}
		}
	}
}


int check(int aa,int bb,int cc,int ee){
	if(aa<=0 or aa>=n-1){
		return 0;
	}
	if(cc<=0 and cc>=n-1){
		return 0;
	}
	if(bb<=0 or bb>=m-1){
		return 0;
	}
	if(ee<=0 and ee>=m-1){
		return 0;
	}
	if(cc<aa or ee<bb){
		return 0;
	}
	/*if(aa==1 and bb==1 and cc==1 and ee==1){
		cout<<11<<endl;
		cout<<re[1][bb-1]<<":"<<le[1][ee+1]<<endl;
	}*/
	for(int i=aa;i<=cc;i++){
		int xx=min(it[i][bb-1],it[i][ee+1]);
		if(xx==it[i][bb-1]){
			if(re[i][bb-1]==ee+1){
				continue;
			}
		}
		if(xx==it[i][ee+1]){
			if(le[i][ee+1]==bb-1){
				continue;
			}
		}
		return 0;
	}
	for(int i=bb;i<=ee;i++){
		int xx=min(it[aa-1][i],it[cc+1][i]);
		if(it[aa-1][i]==xx){
			if(dd[aa-1][i]==cc+1){
				continue;
			}
		}
		if(xx==it[cc+1][i]){
			if(uu[cc+1][i]==aa-1){
				continue;
			}
		}
		return 0;
	}
	//cout<<aa<<":"<<bb<<":"<<cc<<":"<<ee<<endl;
	return 1;
}
llo count_rectangles(vector<vector<int>> ac) {
	it=ac;
	n=it.size();
	m=it[0].size();


	int stt=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(it[i][j]>1){
				stt=0;
			}
		}
	}
	if(stt){
		int co=0;
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				comp.clear();
				if(it[i][j]==0){
					if(vis[i][j]==0){
						dfs(i,j);
						int mi1=0;
						int mi2=n;
						int ma1=0;
						int ma2=m;
						int st=1;
						for(auto jj:comp){
							mi1=max(mi1,jj.a);
							mi2=min(mi2,jj.a);
							ma1=max(ma1,jj.b);
							ma2=min(ma2,jj.b);
							if(jj.a==0 or jj.a==n-1 or jj.b==0 or jj.b==m-1){
								st=0;
							}
						}
						if((int)(comp.size())==(mi1-mi2+1)*(ma1-ma2+1)){
							co+=st;
						//	cout<<i<<":"<<j<<endl;
						}
					}
				}
			}
		}
		return co;
	}


	for(int i=0;i<n;i++){
		vector<pair<int,int>> ss;

		for(int j=0;j<m;j++){
			while(ss.size()){
				if(ss.back().a<it[i][j]){
					ss.pop_back();
				}
				else{
					break;
				}
			}
			le[i][j]=-1;
			if(ss.size()){
				le[i][j]=ss.back().b;
				pre[i][ss.back().b].pb({i,j});
			}
			ss.pb({it[i][j],j});

		}
	}
	for(int i=0;i<n;i++){
		vector<pair<int,int>> ss;

		for(int j=m-1;j>=0;j--){
			while(ss.size()){
				if(ss.back().a<it[i][j]){
					ss.pop_back();
				}
				else{
					break;
				}
			}
			re[i][j]=-1;
			if(ss.size()){
				if(ss.back().a!=it[i][j]){
					re[i][j]=ss.back().b;
				}
			}

			ss.pb({it[i][j],j});
		}
	}
	/*for(int j=0;j<m;j++){
		cout<<re[1][j]<<".";
	}
	cout<<endl;*/

	for(int j=0;j<m;j++){
		vector<pair<int,int>> ss;
		for(int i=0;i<n;i++){
			while(ss.size()){
				if(ss.back().a<it[i][j]){
					ss.pop_back();
				}
				else{
					break;
				}
			}
			uu[i][j]=-1;
			if(ss.size()){
				uu[i][j]=ss.back().b;
			}
			ss.pb({it[i][j],i});
		}
	}
	for(int j=0;j<m;j++){
		vector<pair<int,int>> ss;
		for(int i=n-1;i>=0;i--){
			while(ss.size()){
				if(ss.back().a<it[i][j]){
					ss.pop_back();
				}
				else{
					break;
				}
			}
			dd[i][j]=-1;
			if(ss.size()){
				if(ss.back().a!=it[i][j]){
					dd[i][j]=ss.back().b;
				}
			}
			ss.pb({it[i][j],i});
		}
	}
	llo ans=0;
	for(int i=0;i<n-2;i++){
		for(int j=0;j<m-2;j++){
			int aa,bb,cc,ee;
			aa=i+1;
			bb=j+1;
			if(dd[i][j+1]>-1){
				cc=dd[i][j+1]-1;
				if(cc<aa){
					continue;
				}

				int st=1;
				for(int k=bb;k<m-1;k++){
					ee=k;
					ans=(ans+check(aa,bb,cc,ee));
				}
				continue;
				for(auto jj:pre[i+1][j]){
					ee=jj.b-1;
					if(aa<=cc and bb<=ee){
						/*if(i==3 and j==2){
							cout<<aa<<","<<bb<<","<<cc<<","<<ee<<endl;
						}*/
						ans=ans+check(aa,bb,cc,ee);
						if(jj.b==re[i+1][j]){
							st=0;
						}
					}
				}
				if(re[i+1][j]!=-1){
					ee=re[i+1][j]-1;
					if(aa<=cc and bb<=ee){
						/*if(i==3 and j==2){
							cout<<aa<<","<<bb<<","<<cc<<","<<ee<<endl;
						}*/
						ans=ans+check(aa,bb,cc,ee);
					}
				}
			}
		}
	}
	//cout<<11<<endl;
	for(int i=n-1;i>1;i--){
		for(int j=0;j<m-2;j++){
			if(uu[i][j+1]>-1){
				int aa,bb,cc,ee;
				bb=j+1;
				cc=i-1;
				aa=uu[i][j+1]+1;
				for(int k=bb;k<m-1;k++){
					ee=k;
					ans=(ans+check(aa,bb,cc,ee));
				}
				continue;
				int st=1;
			/*	if(i==2 and j==0){
					cout<<aa<<","<<bb<<","<<cc<<","<<endl;
				}*/
				for(auto jj:pre[aa][bb-1]){
					ee=jj.b-1;
					if(aa<=cc and bb<=ee){
						/*if(i==2 and j==0){
							cout<<aa<<","<<bb<<","<<cc<<","<<ee<<endl;
						}*/
						ans=ans+check(aa,bb,cc,ee);
						if(jj.b==re[aa][cc-1]){
							st=0;
						}
					}
				}
				if(re[aa][bb-1]!=-1){
					ee=re[aa][bb-1]-1;
					if(aa<=cc and bb<=ee){
					/*	if(i==2 and j==0){
							cout<<aa<<","<<bb<<","<<cc<<","<<ee<<endl;
						}*/
						ans=ans+check(aa,bb,cc,ee);
					}
				}

			}
		}
	}
/*	for(int i=1;i<n-1;i++){
		for(int j=1;j<m-1;j++){
			for(int k=i;k<n-1;k++){
				for(int l=j;l<m-1;l++){

					if(check(i,j,k,l)==1){
						cout<<i<<":"<<j<<":"<<k<<":"<<l<<endl;
					}
					ans+=check(i,j,k,l);
				}
			}
		}
	}*/

	/*for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(re[i][j]>j+1){

			}
		}
	}


*/











	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'llo count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:242:9: warning: variable 'st' set but not used [-Wunused-but-set-variable]
  242 |     int st=1;
      |         ^~
rect.cpp:285:9: warning: variable 'st' set but not used [-Wunused-but-set-variable]
  285 |     int st=1;
      |         ^~

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28