Cod sursa(job #467147)

Utilizator FlorianFlorian Marcu Florian Data 28 iunie 2010 12:17:13
Problema Cadrane Scor 50
Compilator cpp Status done
Runda Stelele Informaticii 2010, clasele X-XII, Ziua 2 Marime 2.1 kb
using namespace std;
#include<fstream>
#include<algorithm>
const int MAX_N = 100007, oo = 0x3f3f3f3f;
struct punct { int x,y; };
punct A[MAX_N], B[MAX_N];
int N, H[3 * MAX_N + 2], full[3 * MAX_N + 2];
struct crescator_dupa_x
{
	bool operator()(const punct &a, const punct &b)const
	{
		return a.x < b.x;
	}
};
struct crescator_dupa_y
{
	bool operator()(const punct &a, const punct &b)const
	{
		if(a.y == b.y) return a.x < b.x;
		return a.y < b.y;
	}
};
inline int min( int a, int b) { return a<b?a:b; }
inline int max( int a, int b) { return a>b?a:b; }
void update(int n, int l, int r, int st, int dr, int v)
{
	if( st <= l && r <= dr )
	{
		full[n] += v;
		H[n] += v;
		return;
	}
	int m = ( l+r)>>1;
	if( st <= m ) update( 2*n, l, m, st, dr, v);
	if( dr > m ) update( 2*n+1, m+1, r, st, dr, v);
	H[n] = min( H[2*n], H[2*n+1] ) + full[n];
}
int upper(int Y)
{
	int st = 1, dr = N, m;
	while( st <= dr)
	{
		m = (st + dr)>>1;
		if( B[m].y == Y && ( m == N || B[m+1].y != Y )) return m;
		else if( B[m].y <= Y ) st = m + 1;
		else dr = m - 1;
	}
	return 0;
}
int lower(int Y)
{
	int  st = 1, dr = N, m;
	while( st <= dr)
	{
		m = (st + dr)>>1;
		if( B[m].y == Y && ( m == 1 || B[m-1].y != Y )) return m;
		else if( B[m].y < Y ) st = m + 1;
		else dr = m - 1;
	}
	return 0;
}
int main()
{
	ifstream in("cadrane.in"); ofstream out("cadrane.out");
	in>>N;
	int i, j;
	for(i = 1; i <= N; ++i)
	{
		in>>A[i].x>>A[i].y;
		B[i] = A[i];
	}
	sort( A + 1, A+N+1, crescator_dupa_x());
	sort( B + 1, B+N+1, crescator_dupa_y());
	int cnt = N, tmp = 1;
	for(i = 1; i <= N; ++i)
	{
		update( 1, 1, N, i, i, cnt);
		if( i < N && B[i].y == B[i+1].y ) ++tmp;
		else
		{
			cnt -= tmp;
			tmp = 1;
		}
	}
	int sol = H[1], l, u;
	i = 1;
	while( i <= N && A[1].x == A[i].x ) ++i;
	for(; i <= N; ++i)
	{
		if( A[i].x != A[i-1].x )
		{
			for(j = i - 1; j && A[j].x == A[i-1].x ; --j)
			{
				l = lower( A[j].y );
				u = upper( A[j].y );
				update( 1, 1, N, 1, u, -1);
				update( 1, 1, N, l, N, 1);
			}
			sol = max( sol, H[1] );
		}
	}
	out<<sol<<"\n";
	return 0;
}