Submission #226370

#	Time	Username	Problem	Language	Result	Execution time	Memory
226370		tinjyu	Rectangles (IOI19_rect)	C++14	10 / 100	972 ms	1048576 KiB

rect

#include "rect.h"
#include <iostream>
#include <cmath>
using namespace std;
long long int n,m,s[705][2505][13][2],l[2505][2505],st2[2505][2505][13][2],r[2505][2505],t[10005][2],bits[20];
long long int find1(int i,int j,int l,int r)
{
	if(l==-1 || r==-1)return 0;
	long long int k=log2(r-l+1);
	//cout<<i<<" "<<j<<" "<<l<<" "<<r<<" "<<k<<endl;
	//cout<<s[i][j][k][0]<<" "<<s[i][j][k][1]<<" "<<s[i][r-bits[k]+1][k][0]<<" "<<s[i][r-bits[k]+1][k][1]<<endl;
	if(s[i][j][k][0]!=-1 && s[i][j][k][1]!=-1 && s[i][j][k][0]==s[i][r-bits[k]+1][k][0] && s[i][j][k][1]==s[i][r-bits[k]+1][k][1])return 1;
	return 0;
}
long long int find2(int i,int j,int l,int r)
{
	if(l==-1 || r==-1)return 0;
	long long int k=log2(r-l+1);
	//cout<<i<<" "<<j<<" "<<l<<" "<<r<<" "<<k<<endl;
	//cout<<st2[i][j][k][0]<<" "<<st2[i][j][k][1]<<" "<<st2[r-bits[k]+1][j][k][0]<<" "<<st2[r-bits[k]+1][j][k][1]<<endl; 
	if(st2[i][j][k][0]!=-1 && st2[i][j][k][1]!=-1 && st2[i][j][k][0]==st2[r-bits[k]+1][j][k][0] && st2[i][j][k][1]==st2[r-bits[k]+1][j][k][1])return 1;
	return 0;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
	n=a.size();
	m=a[0].size();
	for(int i=0;i<n;i++)
	{
		long long int p=0,st=0,en=-1;
		for(int j=0;j<m;j++)
		{
			l[i][j]=-1;
			r[i][j]=-1;
			for(int k=en;k>=st;k--)
			{
				if(a[i][j]>t[k][0])
				{
					r[i][t[k][1]]=j;
					en--;
				}
				else 
				{
					en++;
					t[en][0]=a[i][j];
					t[en][1]=j;
					if(a[i][j]<t[k][0])l[i][j]=t[k][1];
					else l[i][j]=l[i][t[k][1]];
					break;
				}
			}
			if(en==-1)
			{
				en=0;
				t[en][0]=a[i][j];
				t[en][1]=j;
			}
			
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			st2[i][j][0][0]=l[i][j];
			st2[i][j][0][1]=r[i][j];
		}
	}
	for(int j=0;j<m;j++)
	{
		long long int p=0,st=0,en=-1;
		for(int i=0;i<n;i++)
		{
			s[i][j][0][0]=-1;
			s[i][j][0][1]=-1;
			for(int k=en;k>=st;k--)
			{
				if(a[i][j]>t[k][0])
				{
					s[t[k][1]][j][0][1]=i;
					en--;
				}
				else 
				{
					en++;
					t[en][0]=a[i][j];
					t[en][1]=i;
					if(a[i][j]<t[k][0])s[i][j][0][0]=t[k][1];
					else s[i][j][0][0]=s[t[k][1]][j][0][0];
					break;
				}
			}
			if(en==-1)
			{
				en=0;
				t[en][0]=a[i][j];
				t[en][1]=i;
			}
			
		}
	}
	bits[0]=1;
	for(int i=1;i<=15;i++)bits[i]=bits[i-1]*2;
	for(int k=1;bits[k]<=m;k++)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(j+bits[k-1]>=m)break;
				if( s[i][j][k-1][0]==s[i][j+bits[k-1]][k-1][0] && s[i][j][k-1][1]==s[i][j+bits[k-1]][k-1][1] && s[i][j][k-1][0]!=-1 && s[i][j][k-1][0]!=-1)
				{
					s[i][j][k][0]=s[i][j][k-1][0];
					s[i][j][k][1]=s[i][j][k-1][1];
				}
				else
				{
					s[i][j][k][0]=-1;
					s[i][j][k][1]=-1;
				}
				//cout<<i<<" "<<j<<" "<<k<<" "<<s[i][j][k][0]<<" "<<s[i][j][k][1]<<endl;
			}
		}
	}
	for(int k=1;bits[k]<=n;k++)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(i+bits[k-1]>=n)break;
				if( st2[i][j][k-1][0]==st2[i+bits[k-1]][j][k-1][0] && st2[i][j][k-1][1]==st2[i+bits[k-1]][j][k-1][1] && st2[i][j][k-1][0]!=-1 && st2[i][j][k-1][1]!=-1)
				{
					st2[i][j][k][0]=st2[i][j][k-1][0];
					st2[i][j][k][1]=st2[i][j][k-1][1];
				}
				else
				{
					st2[i][j][k][0]=-1;
					st2[i][j][k][1]=-1;
				}
				//cout<<i<<" "<<j<<" "<<k<<" "<<st2[i][j][k][0]<<" "<<st2[i][j][k][1]<<endl;
			}
		}
	}
	long long int ans=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(l[i][j]==-1 || r[i][j]==-1 || st2[i][j][0][0]==-1 || st2[i][j][0][1]==-1)continue;
			long long int ri=l[i][j]+1,le=s[i][j][0][0]+1;
			if(find1(le,ri,l[i][j]+1,r[i][j]-1)+find2(le,ri,s[i][j][0][0]+1,s[i][j][0][1]-1)==2)ans++;
			//cout<<ans<<endl;
		}
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:29:17: warning: unused variable 'p' [-Wunused-variable]
   long long int p=0,st=0,en=-1;
                 ^
rect.cpp:70:17: warning: unused variable 'p' [-Wunused-variable]
   long long int p=0,st=0,en=-1;
                 ^

• 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