제출 #1033985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1033985		amirhoseinfar1385	Rectangles (IOI19_rect)	C++17	0 / 100	43 ms	2172 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2500+10,ted=8;
int all[maxn][maxn],vis[maxn][maxn],tp[maxn][maxn],n,m;
set<pair<pair<int,int>,pair<int,int>>>kol;
set<int>st[maxn],str[maxn];
vector<int>dx={-1,-1,-1,0,1,1,1,0},dy={-1,0,1,1,1,0,-1,-1};

void besh(int i,int j){
	if(vis[i][j]){
		return ;
	}
	int tlr=i,trr=i,tlc=j,trc=j;
	auto xc=st[j].lower_bound(i);
	trr=*xc;
	xc--;
	tlr=*xc;
	auto xr=str[i].lower_bound(j);
	trc=*xr;
	xr--;
	tlc=*xr;
	int cnt=0;
	for(int h=tlc+1;h<trc;h++){
		cnt+=vis[tlr][h]+vis[trr][h];
	}
	for(int h=tlr+1;h<trr;h++){
		cnt+=vis[h][tlc]+vis[h][trc];
	}
	if(cnt!=(trr-tlr-1)*2+(trc-tlc-1)*2){
		return ;
	}
	int mina=n+1;
	for(int h=tlc+1;h<trc;h++){
		mina=min(mina,tp[tlr][h]);
	}
	if(mina!=trr){
		return ;
	}
	kol.insert(make_pair(make_pair(tlr,tlc),make_pair(trr,trc)));
}

void ins(int i,int j){
	vis[i][j]=1;
	auto x=st[j].lower_bound(i);
	tp[i][j]=*x;
	x--;
	tp[*x][j]=i;
	st[j].insert(i);
	str[i].insert(j);
	for(int h=0;h<ted;h++){
		besh(i+dx[h],j+dy[h]);
	}
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	n=a.size();
	m=a[0].size();
	for(int i=0;i<maxn;i++){
		st[i].insert(0);
		st[i].insert(n+1);
		str[i].insert(0);
		str[i].insert(m+1);
	}
	vector<pair<int,pair<int,int>>>v;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			all[i][j]=a[i-1][j-1];
			v.push_back(make_pair(all[i][j],make_pair(i,j)));
		}
	}
	sort(v.rbegin(),v.rend());
	for(int i=0;i<(int)v.size();i++){
		ins(v[i].second.first,v[i].second.second);
	}
	return (int)kol.size();
}

• 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