Submission #200951

#	Time	Username	Problem	Language	Result	Execution time	Memory
200951		Lawliet	Rectangles (IOI19_rect)	C++17	59 / 100	5057 ms	692932 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 = 2510;
const int INF = 1000000010;

class SegmentTree
{
	public:

		int getLeft(int node) { return 2*node; }
		int getRight(int node) { return 2*node + 1; }

		void update(int node, int l, int r, int i, int v)
		{
			if( i < l || r < i ) return;

			if( l == r )
			{
				mx[ node ] = v;
				return;
			}

			int m = ( l + r )/2;

			update( getLeft(node) , l , m , i , v );
			update( getRight(node) , m + 1 , r , i , v );

			mx[node] = max( mx[ getLeft(node) ] , mx[ getRight(node) ] );
		}

		int query(int node, int l, int r, int i, int j)
		{
			if( j < l || r < i ) return -INF;
			if( i <= l && r <= j ) return mx[node];

			int m = ( l + r )/2;

			int mxLeft = query( getLeft(node) , l , m , i , j );
			int mxRight = query( getRight(node) , m + 1 , r , i , j );

			return max( mxLeft , mxRight );
		}

		SegmentTree()
		{
			for(int i = 0 ; i < 4*MAXN ; i++)
				mx[i] = -INF;
		}

	private:

		int mx[4*MAXN];
};

int n, m;

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

SegmentTree mnR[MAXN];
SegmentTree mxL[MAXN];
SegmentTree mxUp[MAXN];
SegmentTree mnDown[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][0];

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

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

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

			R[i][j][1] = 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][0];

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

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

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

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

void preProcess()
{
	for(int i = 1 ; i <= n ; i++)
	{
		for(int j = 1 ; j <= m ; j++)
		{
			mnR[j].update( 1 , 1 , n , i , -R[i][j][1] );
			mxL[j].update( 1 , 1 , n , i , L[i][j] );

			//printf("j = %d    i = %d    %d\n",i,j,-R[i][j][1]);

			mxUp[i].update( 1 , 1 , m , j , up[i][j] );
			mnDown[i].update( 1 , 1 , m , j , -down[i][j][1] );
		}
	}
}

bool isAnswer(int x1, int y1, int x2, int y2)
{
	int mnRight = -mnR[y1 - 1].query( 1 , 1 , n , x1 , x2 );
	int mxLeft = mxL[y2 + 1].query( 1 , 1 , n , x1 , x2 );

	int mxCurUp = mxUp[x2 + 1].query( 1 , 1 , m , y1 , y2 );
	int mnCurDown = -mnDown[x1 - 1].query( 1 , 1 , m , y1 , y2 );

	//printf("==== %d %d %d %d\n",x1,y1,x2,y2);
	//printf("........ %d %d %d %d\n",mnRight,mxLeft,mxCurUp,mnCurDown);

	if( mnRight <= y2 ) return false;
	if( y1 <= mxLeft ) return false;

	//printf("oi\n");

	if( mnCurDown <= x2 ) return false;
	if( x1 <= mxCurUp ) return false;

	//printf("pa\n");

	return true;
}

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][0] == m + 1 ) continue;

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

			pii dY = { L[i][j] + 1 , R[i][j][0] - 1 };
			pii dX = { up[i][j] + 1 , down[i][j][0] - 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:216:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < aux.size() ; i++)
                  ~~^~~~~~~~~~~~
rect.cpp:221: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: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28