Submission #200952

#	Time	Username	Problem	Language	Result	Execution time	Memory
200952		Lawliet	Rectangles (IOI19_rect)	C++17	0 / 100	263 ms	395640 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 = 2 ; i < n ; i++)
	{
		for(int j = 2 ; 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: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28