Cod sursa(job #491740)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 12 octombrie 2010 11:21:47
Problema Cadrane Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 100005
#define pb push_back
using namespace std;
struct pct
{
	int a,b;
};
pct A[NMAX],ord[NMAX];
int n,C[NMAX],D[NMAX],r,t,rez;
vector <int> E[NMAX],F[NMAX];
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
	{
		scanf("%d%d",&A[i].a,&A[i].b);
		C[++r]=A[i].a; D[++t]=A[i].b;
	}
}
int cbin1(int x)
{
	int i,step=(1<<16);
	for (i=0; step; step>>=1)
		if (i+step<=r && C[i+step]<=x)
			i+=step;
	return i;
}
int cbin2(int x)
{
	int i,step=(1<<16);
	for (i=0; step; step>>=1)
		if (i+step<=t && D[i+step]<=x)
			i+=step;
	return i;
}
void normalizare()
{
	int i,poz=1;
	sort(C+1,C+r+1);
	sort(D+1,D+t+1);
	for (i=2; i<=r; i++)
		if (C[i]!=C[i-1])
			C[++poz]=C[i];
	r=poz;
	poz=1;
	for (i=2; i<=t; i++)
		if (D[i]!=D[i-1])
			D[++poz]=D[i];
	t=poz;
	for (i=1; i<=n; i++)
	{
		A[i].a=cbin1(A[i].a);
		A[i].b=cbin2(A[i].b);
		E[A[i].a].pb(i);
		F[A[i].b].pb(i);
	}
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
void solve()
{
	int i,j,k,act,nr,poz;
	for (i=1; i<=t; i++)
	{
		nr=0;
		for (j=1; j<=n; j++)
			if (A[j].b<=i)
				nr++;
		act=nr;
		for (j=2; j<=r; j++)
		{
			for (k=0; k<E[j-1].size(); k++)
			{
				poz=E[j-1][k];
				if (A[poz].b<i) 
					nr--;
			}
			for (k=0; k<E[j].size(); k++)
			{
				poz=E[j][k];
				if (A[poz].b>i)
					nr++;
			}
			act=min(act,nr);
		}
		if (rez<act)
			rez=act;
	}
}
int main()
{
	freopen("cadrane.in","r",stdin);
	freopen("cadrane.out","w",stdout);
	read();
	normalizare();
	solve();
	printf("%d\n",rez);
	return 0;
}