Submission #200950

#	Time	Username	Problem	Language	Result	Execution time	Memory
200950		Lawliet	Rectangles (IOI19_rect)	C++17	27 / 100	5100 ms	539808 KiB

rect

#include <bits/stdc++.h>
#include "rect.h"

using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;

const int MAXN = 710;
const int INF = 1000000010;

int n, m;

int v[MAXN][MAXN];
int L[MAXN][MAXN];
int R[MAXN][MAXN];
int up[MAXN][MAXN];
int down[MAXN][MAXN];

vector< int > sumPossibleLine[MAXN][MAXN];
vector< int > sumPossibleColumn[MAXN][MAXN];

void makeHistogram()
{
	for(int i = 1 ; i <= n ; i++)
	{
		v[i][0] = v[i][m + 1] = INF;

		for(int j = 1 ; j <= m ; j++)
		{
			int cur = j - 1;

			while( v[i][cur] < v[i][j] ) cur = L[i][cur];

			L[i][j] = cur;
		}

		for(int j = m ; j > 0 ; j--)
		{
			int cur = j + 1;

			while( v[i][cur] <= v[i][j] ) cur = R[i][cur];

			R[i][j] = cur;
		}
	}

	for(int j = 1 ; j <= m ; j++)
	{
		v[0][j] = v[n + 1][j] = INF;

		for(int i = 1 ; i <= n ; i++)
		{
			int cur = i - 1;

			while( v[cur][j] < v[i][j] ) cur = up[cur][j];

			up[i][j] = cur;
		}

		for(int i = n ; i > 0 ; i--)
		{
			int cur = i + 1;

			while( v[cur][j] <= v[i][j] ) cur = down[cur][j];

			down[i][j] = cur;
		}
	}
}

void preProcess()
{
	for(int i = 1 ; i <= m ; i++)
		for(int j = 1 ; j <= m ; j++)
			sumPossibleLine[i][j].push_back( 0 ), sumPossibleLine[i][j].push_back( 0 );

	for(int i = 2 ; i < n ; i++)
	{
		for(int y1 = 2 ; y1 < m ; y1++)
		{
			int mx = v[i][y1];

			for(int y2 = y1 ; y2 < m ; y2++)
			{
				int val = 0;
				if( mx < v[i][y1 - 1] && mx < v[i][y2 + 1] ) val = 1;

				sumPossibleLine[y1][y2].push_back( sumPossibleLine[y1][y2].back() + val );

				if( y2 >= m - 1 ) break;

				mx = max( mx , v[i][y2 + 1] );
			}
		}
	}

	for(int i = 1 ; i <= m ; i++)
		for(int j = 1 ; j <= m ; j++)
			sumPossibleLine[i][j].push_back( sumPossibleLine[i][j].back() );

	for(int i = 1 ; i <= n ; i++)
		for(int j = 1 ; j <= n ; j++)
			sumPossibleColumn[i][j].push_back( 0 ), sumPossibleColumn[i][j].push_back( 0 );

	for(int i = 2 ; i < m ; i++)
	{
		for(int x1 = 2 ; x1 < n ; x1++)//Ver n == 2 ou n == 3
		{
			int mx = v[x1][i];

			for(int x2 = x1 ; x2 < n ; x2++)
			{
				int val = 0;
				if( mx < v[x1 - 1][i] && mx < v[x2 + 1][i] ) val = 1;

				sumPossibleColumn[x1][x2].push_back( sumPossibleColumn[x1][x2].back() + val );

				if( x2 >= n - 1 ) break;

				mx = max( mx , v[x2 + 1][i] );
			}
		}
	}

	for(int i = 1 ; i <= n ; i++)
		for(int j = 1 ; j <= n ; j++)
			sumPossibleColumn[i][j].push_back( sumPossibleColumn[i][j].back() );
}

bool isAnswer(int x1, int y1, int x2, int y2)
{
	int s = sumPossibleLine[y1][y2][x2] - sumPossibleLine[y1][y2][x1 - 1];

	if( s != x2 - x1 + 1 ) return false;

	s = sumPossibleColumn[x1][x2][y2] - sumPossibleColumn[x1][x2][y1 - 1];

	return ( s == y2 - y1 + 1 );
}

long long count_rectangles(vector< vector<int> > a) //Grids pequenos
{
	n = a.size();
	m = a[0].size();

	for(int i = 0 ; i < n ; i++)
		for(int j = 0 ; j < m ; j++)
			v[i + 1][j + 1] = a[i][j];

	makeHistogram();

	vector< pair<pii,pii> > aux;
	vector< pair<pii,pii> > rect;

	for(int i = 2 ; i < n ; i++)
	{
		for(int j = 2 ; j < m ; j++)
		{
			if( L[i][j] == 0 ) continue;
			if( R[i][j] == m + 1 ) continue;

			if( up[i][j] == 0 ) continue;
			if( down[i][j] == n + 1 ) continue;

			pii dY = { L[i][j] + 1 , R[i][j] - 1 };
			pii dX = { up[i][j] + 1 , down[i][j] - 1 };

			aux.push_back( { dX , dY } );
		}
	}

	preProcess();

	sort( aux.begin() , aux.end() );

	for(int i = 0 ; i < aux.size() ; i++)
		if( i == 0 || aux[i] != aux[i - 1] ) rect.push_back( { aux[i] } );

	lli ans = 0;

	for(int i = 0 ; i < rect.size() ; i++)
	{
		int x1 = rect[i].first.first;
		int x2 = rect[i].first.second;
		int y1 = rect[i].second.first;
		int y2 = rect[i].second.second;

		if( isAnswer( x1 , y1 , x2 , y2 ) ) ans++;
	}

	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:176:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < aux.size() ; i++)
                  ~~^~~~~~~~~~~~
rect.cpp:181:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < rect.size() ; i++)
                  ~~^~~~~~~~~~~~~

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