Submission #1237204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237204		Muhammad_Aneeq	Rectangles (IOI19_rect)	C++20	13 / 100	1615 ms	286144 KiB

rect

#include "rect.h"
#include <vector>
#include <iostream>
#include <map>
#include <set>
using namespace std;
#define ll long long
int const NM=2500*2500*+10;
struct comp
{
	int sz,l,r,u,d;	
};
int n,m;
comp rec[NM]={};
int par[NM]={};
int x[4];
int root(int n)
{
	return (par[n]==n?n:(par[n]=root(par[n])));
}
comp comb(comp a,comp b)
{
	comp c;
	c.sz=a.sz+b.sz;
	c.l=min(a.l,b.l);
	c.r=max(a.r,b.r);
	c.u=min(a.u,b.u);
	c.d=max(a.d,b.d);
	return c;
}
vector<int>vals;
bool valid(comp a)
{
	if (a.l==0||a.u==0||a.d==n-1||a.r==m-1)
		return 0;
	ll lv=(a.d-a.u)+1,lh=(a.r-a.l)+1;
	return ((lv*lh)==a.sz);
}
bool ma(int i,int j)
{
	if (j<0||j>=n*m||vals[j]>vals[i])
		return 0;
	return 1;
}
bool merge(int u,int v)
{
	u=root(u);
	v=root(v);
	if (u==v)
		return 1;
	rec[u]=comb(rec[u],rec[v]);
	par[v]=u;
	return valid(rec[u]);
}
long long count_rectangles(vector<vector<int>>a) 
{
	n=a.size(),m=a[0].size();
	x[0]=m,x[1]=-m,x[2]=-1,x[3]=1;
	map<int,vector<int>>ind;
	set<int>s;
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<m;j++)
		{
			vals.push_back(a[i][j]);
			int nm=i*m+j;
			par[nm]=nm;
			rec[nm].sz=1;
			rec[nm].l=rec[nm].r=j;
			rec[nm].u=rec[nm].d=i;
			s.insert(a[i][j]);
			ind[a[i][j]].push_back(nm);
		}
	}
	long long ans=0;
	for (auto i:s)
	{
		set<int>g;
		for (auto j:ind[i])
		{
			for (auto k:x)
			{
				if (ma(j,j+k))
				{
					merge(j,j+k);
				}
			}
			g.insert(root(j));
		}
		for (auto i:g)
		{
			if (i!=root(i)||!valid(rec[i]))
				continue;
			// cout<<i<<endl;
			ans++;
		}
	}
	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