oj.uz

Submission #1034000

# Submission time Handle Problem Language Result Execution time Memory
1034000 2024-07-25T08:34:06 Z amirhoseinfar1385 Rectangles (IOI19_rect) C++17
0 / 100
 21 ms 2140 KB 
#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]||i<1||i>n||j<1||j>m){
		return ;
	}
	int tlr=i,trr=i,tlc=j,trc=j;
	auto xc=st[j].lower_bound(i);
	trr=*xc;
	xc--;
	tlr=*xc;
	//cout<<i<<" "<<tlr<<" "<<trr<<endl;
	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);
	}
//	for(auto x:kol){
//		cout<<x.first.first<<" "<<x.first.second<<" "<<x.second.first<<" "<<x.second.second<<endl;
//	}
	return (int)kol.size();
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2100 KB Output is correct
2 Correct 15 ms 2140 KB Output is correct
3 Correct 18 ms 1884 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Incorrect 6 ms 2140 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -