Submission #891498

#	Time	Username	Problem	Language	Result	Execution time	Memory
891498		Muhammad_Aneeq	Rectangles (IOI19_rect)	C++17	10 / 100	303 ms	10980 KiB

rect

/*
بسم الله الرحمن الرحيم
Author:
                          (:Muhammad Aneeq:)
*/
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <vector>
#include <iostream>
using namespace std;
int const N=2600;
struct segt
{
	vector<int>a;
	int seg[4*N];
	segt(vector<int>&s)
	{
		a=s;
		build(1,0,a.size()-1);
	}	
	void build(int i,int st,int en)
	{
		if (st==en)
		{
			seg[i]=a[st];
			return;
		}
		int mid=(st+en)/2;
		build(i*2,st,mid);build(i*2+1,mid+1,en);
		seg[i]=max(seg[i*2],seg[i*2+1]);
	}
	int get(int i,int l,int r,int st,int en)
	{
		if (st>=l&&en<=r)
			return seg[i];
		if (st>r||en<l)
			return 0;
		int mid=(st+en)/2;
		return max(get(i*2,l,r,st,mid),get(i*2+1,l,r,mid+1,en));
	}
};
segt* St[2][N]={NULL};
long long count_rectangles(vector<vector<int>>a)
{
	int n=a.size(),m=a[0].size();
	for (int i=0;i<n;i++)
		St[0][i]=new segt(a[i]);
	bool w=0;
	for (int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
			if (a[i][j]>1)
				w=1;
	}
	if (w==0)
	{
		int pre[n+1][m+1]={};
		for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
				pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i-1][j-1];
		long long ans=0;
		for (int i=1;i<n-1;i++)
		{
			for (int j=1;j<m-1;j++)
			{
				if (a[i][j]==0&&a[i][j-1]==1&&a[i-1][j]==1)
				{
					int st=i,en=n;
					while (st+1<en)
					{
						int mid=(st+en)/2;
						if (pre[mid+1][j+1]-pre[mid+1][j]-pre[i][j+1]+pre[i][j]==0)
						{
							st=mid;
						}
						else
							en=mid;
					}
					if (st==n-1)
						continue;
					int k=st;
					st=j,en=m-1;
					while (st+1<en)
					{
						int mid=(st+en)/2;
						if (pre[k+1][mid+1]-pre[k+1][j]-pre[i][mid+1]+pre[i][j]==0)
							st=mid;
						else
							en=mid;
					}
					if (st==m-1)
						continue;
					int l=st;
					if (pre[k+1][l+1]-pre[i][l+1]-pre[k+1][j]+pre[i][j]==0)
						ans++;
				}
			}
		}
		return ans;
	}
	for (int i=0;i<m;i++)
	{
		vector<int>z;
		for (int j=0;j<n;j++)
			z.push_back(a[j][i]);
		St[1][i]=new segt(z);
	}
	long long ans=0;
	for (int i=1;i<n-1;i++)
	{
		for (int j=1;j<m-1;j++)
		{
			for (int k=i;k<n-1;k++)
			{
				for (int l=j;l<m-1;l++)
				{
					bool w=0;
					for (int o=i;o<=k&&!w;o++)
					{
						int f=St[0][o]->get(1,j,l,0,m-1);
						if (f>=a[o][j-1]||f>=a[o][l+1])
							w=1;
					}
					for (int o=j;o<=l&&!w;o++)
					{
						int f=St[1][o]->get(1,i,k,0,n-1); 
						if (f>=a[i-1][o]||f>=a[k+1][o])
							w=1;
					}
					ans+=(!w);
				}
			}
		}
	}
	return ans;
}

• 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