Submission #1153280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153280		owoovo	Rectangles (IOI19_rect)	C++20	13 / 100	1453 ms	434412 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
#define ll long long 
#define F first 
#define S second 
using namespace std;
pair<int,int> dsu[2510][2510];
int sz[2510][2510],nl[2510][2510],xr[2510][2510],nu[2510][2510],xd[2510][2510],use[2510][2510],mp[2510][2510],n,m;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
ll ans;
pair<int,int> f(pair<int,int> p){
	auto [x,y]=p;
	if(dsu[x][y]==p){
		return p;
	}else{
		dsu[x][y]=f(dsu[x][y]);
	}
	return dsu[x][y];
}
bool onion(pair<int,int> p1,pair<int,int> p2){
	p1=f(p1);
	p2=f(p2);
	if(p1==p2)return 0;
	auto [x1,y1]=p1;
	auto [x2,y2]=p2;
	if(sz[x1][y1]>sz[x2][y2])swap(p1,p2),swap(x1,x2),swap(y1,y2);
	dsu[x1][y1]=dsu[x2][y2];
	sz[x2][y2]+=sz[x1][y1];
	nl[x2][y2]=min(nl[x1][y1],nl[x2][y2]);
	xr[x2][y2]=max(xr[x1][y1],xr[x2][y2]);
	nu[x2][y2]=min(nu[x1][y1],nu[x2][y2]);
	xd[x2][y2]=max(xd[x1][y1],xd[x2][y2]);
	return 1;
}
ll count_rectangles(vector<vector<int>> a) {
	n=a.size();
	m=a[0].size();
	ans=0;
	vector<pair<int,pair<int,int>>> pt;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			mp[i][j]=a[i-1][j-1];
			dsu[i][j]={i,j};
			sz[i][j]=1;
			nl[i][j]=j;
			xr[i][j]=j;
			nu[i][j]=i;
			xd[i][j]=i;
			pt.push_back({mp[i][j],{i,j}});
		}
	}
	sort(pt.begin(),pt.end());
	pt.push_back({-1,{0,0}});
	vector<pair<int,int>> god;
	for(int i=0;i<n*m;i++){
		if(pt[i].F!=pt[i+1].F){
			for(auto &x:god){
				x=f(x);
			}
			sort(god.begin(),god.end());
			god.erase(unique(god.begin(),god.end()),god.end());
			for(auto x:god){
				auto [u,v]=x;
				if(sz[u][v]==(xr[u][v]-nl[u][v]+1)*(xd[u][v]-nu[u][v]+1)
				&&xr[u][v]!=m&&nl[u][v]!=1&&xd[u][v]!=n&&nu[u][v]!=1)ans++;
			}
			god.clear();
		}
		auto [x,y]=pt[i].S;
		god.push_back({x,y});
		use[x][y]=1;
		for(int c=0;c<4;c++){
			int nx=x+dx[c],ny=y+dy[c];
			if(use[nx][ny]){
				onion({x,y},{nx,ny});
			}
		}
	}

	return ans;
}

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