Submission #1237166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237166		Muhammad_Aneeq	Rectangles (IOI19_rect)	C++17	10 / 100	1135 ms	1021576 KiB

rect

#include "rect.h"
#include <vector>
#include <iostream>
#include <map>
#include <set>
#include <cmath>
using namespace std;
#define ll long long
#define pii pair<int,int>
int const N=2510,LG=12;
struct spmx //sparse table for max
{
	int sp[N][LG]={};
	spmx(vector<int>vals)
	{
		int n=vals.size();
		for (int i=0;i<n;i++)
			sp[i][0]=vals[i];
		for (int j=1;(1<<j)<=n;j++)
			for (int i=0;i+(1<<j)-1<n;i++)
				sp[i][j]=max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
	}
	int get(int l,int r)
	{
		if (l>r)
			return 1e9;
		int lg=log2(r-l+1);
		return max(sp[l][lg],sp[r+1-(1<<lg)][lg]);
	}
};
struct spmn //sparse table for min
{
	int sp[N][LG]={};
	spmn(vector<int>vals)
	{
		int n=vals.size();
		for (int i=0;i<n;i++)
			sp[i][0]=vals[i];
		for (int j=1;(1<<j)<=n;j++)
			for (int i=0;i+(1<<j)-1<n;i++)
				sp[i][j]=min(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
	}
	int get(int l,int r)
	{
		if (l>r)
			return 0;
		int lg=log2(r-l+1);
		return min(sp[l][lg],sp[r+1-(1<<lg)][lg]);
	}
};
int l[N][N],r[N][N],u[N][N],d[N][N]={};
int n,m;int x[4];
vector<spmn>ml,md;
vector<spmx>mr,mu;
bool check(int u,int d,int l,int r)
{
	if (u==0||d==n-1||l==0||r==m-1)
		return 0;
	if (md[u-1].get(l,r)<d)
		return 0;
	if (mu[d+1].get(l,r)>u)
		return 0;
	if (ml[r+1].get(u,d)>l)
		return 0;
	if (mr[l-1].get(u,d)<r)
		return 0;
	return 1;
}
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;
	vector<spmx>rw,cl;
	for (int i=0;i<n;i++)
	{
		vector<int>x;
		for (int j=0;j<m;j++)
			x.push_back(a[i][j]);
		rw.push_back(spmx(x));
	}
	for (int i=0;i<m;i++)
	{
		vector<int>x;
		for (int j=0;j<n;j++)
			x.push_back(a[j][i]);
		cl.push_back(spmx(x));
	}
	set<pair<pii,pii>>ans;
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<m;j++)
		{
			{// right
				int st=j,en=m;
				while (st+1<en)
				{
					int mid=(st+en)/2;
					if (rw[i].get(j+1,mid)>=a[i][j])
						en=mid;
					else
						st=mid;
				}
				r[i][j]=st;
			}
			{// left
				int st=-1,en=j;
				while (st+1<en)
				{
					int mid=(st+en)/2;
					if (rw[i].get(mid,j-1)>=a[i][j])
						st=mid;
					else
						en=mid;
				}
				l[i][j]=en;
			}
			{// up
				int st=-1,en=i;
				while (st+1<en)
				{
					int mid=(st+en)/2;
					if (cl[j].get(mid,i-1)>=a[i][j])
						st=mid;
					else
						en=mid;
				}
				u[i][j]=en;
			}
			{// down
				int st=i,en=n;
				while (st+1<en)
				{
					int mid=(st+en)/2;
					if (cl[j].get(i+1,mid)>=a[i][j])
						en=mid;
					else
						st=mid;
				}
				d[i][j]=st;
			}
			// cout<<u[i][j]<<' '<<d[i][j]<<' '<<l[i][j]<<' '<<r[i][j]<<endl;
		}
	}
	for (int i=0;i<n;i++)
	{
		vector<int>u1,d1;
		for (int j=0;j<m;j++)
		{
			u1.push_back(u[i][j]);
			d1.push_back(d[i][j]);
		}
		mu.push_back(spmx(u1));
		md.push_back(spmn(d1));
	}
	for (int i=0;i<m;i++)
	{
		vector<int>l1,r1;
		for (int j=0;j<n;j++)
		{
			l1.push_back(l[j][i]);
			r1.push_back(r[j][i]);
		}
		ml.push_back(spmn(l1));
		mr.push_back(spmx(r1));
	}
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<m;j++)
		{
			{// right
				int st=j,en=m;
				while (st+1<en)
				{
					int mid=(st+en)/2;
					if (rw[i].get(j,mid)>a[i][j])
						en=mid;
					else
						st=mid;
				}
				r[i][j]=st;
			}
			{// left
				int st=-1,en=j;
				while (st+1<en)
				{
					int mid=(st+en)/2;
					if (rw[i].get(mid,j)>a[i][j])
						st=mid;
					else
						en=mid;
				}
				l[i][j]=en;
			}
			{// up
				int st=-1,en=i;
				while (st+1<en)
				{
					int mid=(st+en)/2;
					if (cl[j].get(mid,i)>a[i][j])
						st=mid;
					else
						en=mid;
				}
				u[i][j]=en;
			}
			{// down
				int st=i,en=n;
				while (st+1<en)
				{
					int mid=(st+en)/2;
					if (cl[j].get(i,mid)>a[i][j])
						en=mid;
					else
						st=mid;
				}
				d[i][j]=st;
			}
		}
	}
	for (int i=1;i<n-1;i++)
	{
		for (int j=1;j<m-1;j++)
		{
			// cout<<i<<' '<<j<<endl;
			// cout<<u[i][j]<<' '<<d[i][j]<<' '<<l[i][j]<<' '<<r[i][j]<<endl;
			if (check(u[i][j],d[i][j],l[i][j],r[i][j]))
			{
				ans.insert({{u[i][j],d[i][j]},{l[i][j],r[i][j]}});
			}
		}
	}
	return ans.size();
}

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