Submission #286090

#	Time	Username	Problem	Language	Result	Execution time	Memory
286090		kshitij_sodani	Rectangles (IOI19_rect)	C++14	31 / 100	772 ms	404948 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;
vector<int> x={1,-1,0,0};
vector<int> y={0,0,-1,1};
int vis[2501][2501];
int n,m;
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 val[201][201][201];
int val2[201][201][201];
bool val3[71][71][71][71];
bool val4[71][71][71][71];
llo count_rectangles(vector<vector<int>> ac) {
	it=ac;
	/*for(auto j:ac){
		for(auto i:j){
			cout<<i<<".";
		}
		cout<<endl;
	}*/
	n=it.size();
	m=it[0].size();
	if(n<=2 or m<=2){
		return 0;
	}
	if(n==3){
		llo co=0;
		for(int i=1;i<m-1;i++){
			int ma=it[1][i];

			for(int j=i;j<m-1;j++){
				if(it[1][j]>=min(it[0][j],it[2][j])){
					break;
				}
				ma=max(ma,it[1][j]);
				if(ma<min(it[1][i-1],it[1][j+1])){
					co+=1;
				}
			}
		}
		return co;
	}
	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 j=1;j<m-1;j++){
		for(int i=1;i<n-1;i++){
			int ma=it[i][j];
			for(int ii=i;ii<n-1;ii++){
				ma=max(ma,it[ii][j]);
				if(ma<min(it[i-1][j],it[ii+1][j])){
					val[j][i][ii]=1;
				}
			}
		}
	}
	for(int j=1;j<n-1;j++){
		for(int i=1;i<m-1;i++){
			int ma=it[j][i];
			for(int ii=i;ii<m-1;ii++){
				ma=max(ma,it[j][ii]);
				if(ma<min(it[j][i-1],it[j][ii+1])){
					val2[j][i][ii]=1;
				}
			}
		}
	}
	for(int j=1;j<m-1;j++){
		for(int i=1;i<n-1;i++){
			for(int ii=i;ii<n-1;ii++){
				for(int jj=j;jj<m-1;jj++){
					if(val[jj][i][ii]==0){
						break;
					}
					val3[i][ii][j][jj]=1;
				}
			}
		}
	}
	llo ans2=0;
	for(int j=1;j<n-1;j++){
		for(int i=1;i<m-1;i++){
			for(int ii=i;ii<m-1;ii++){
				for(int jj=j;jj<n-1;jj++){
					if(val2[jj][i][ii]==0){
						break;
					}
					val3[j][jj][i][ii]&=1;
					ans2+=val3[j][jj][i][ii];
				}
			}
		}
	}

	

	












	return ans2;
}

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