Cod sursa(job #516727)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 25 decembrie 2010 23:37:24
Problema Cadrane Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#define NMAX 100005
#define LMAX 1<<18
#define pb push_back
using namespace std;
int n;
struct pct{int a,b;};
pct A[NMAX];
int B[NMAX],C[NMAX],r,t,F[NMAX],rez,init[NMAX],a,b,value;
vector <int> D[NMAX],E[NMAX];
struct arbint{int a,b;};
arbint arb[LMAX];
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
	{
		scanf("%d%d",&A[i].a,&A[i].b);
		B[++r]=A[i].a;
		C[++t]=A[i].b;
	}
	sort(B+1,B+r+1);
	sort(C+1,C+t+1);
}
inline int cb1(int val)
{
	int i,step=(1<<16);
	for (i=0; step; step>>=1)
		if (i+step<=r && B[i+step]<=val)
			i+=step;
	return i;
}
inline int cb2(int val)
{
	int i,step=(1<<16);
	for (i=0; step; step>>=1)
		if (i+step<=t && C[i+step]<=val)
			i+=step;
	return i;
}
void normalizare()
{
	int i,poz=1;
	for (i=2; i<=r; i++)
		if (B[i]!=B[i-1])
			B[++poz]=B[i];
	r=poz;
	
	poz=1;
	for (i=2; i<=t; i++)
		if (C[i]!=C[i-1])
			C[++poz]=C[i];
	t=poz;
	
	for (i=1; i<=n; i++)
	{
		A[i].a=cb1(A[i].a);
		A[i].b=cb2(A[i].b);
		D[A[i].a].pb(A[i].b);
		E[A[i].b].pb(A[i].a);
	}
}
inline int min(int x,int y)
{
	return x<y ? x : y;
}
inline int max(int x,int y)
{
	return x>y ? x : y;
}
void cstr(int st,int dr,int nod)
{
	if (st==dr)
	{
		init[st]=nod;
		return ;
	}
	int mij=(st+dr)/2;
	cstr(st,mij,nod*2);
	cstr(mij+1,dr,nod*2+1);
}
void update1(int poz,int val)
{
	arb[poz].a=val;
	int i;
	for (i=poz/2; i>0; i/=2)
		arb[i].a=min(arb[2*i].a,arb[2*i+1].a);
}
void update2(int st,int dr,int nod)
{
	if (dr<a || b<st)
		return ;
	if (a<=st && dr<=b)
	{
		arb[nod].b+=value;
		return ;
	}
	int mij=(st+dr)/2;
	update2(st,mij,nod*2);
	update2(mij+1,dr,nod*2+1);
	if (arb[2*nod].a+arb[2*nod].b<arb[2*nod+1].a+arb[2*nod+1].b)
		arb[nod].a=arb[2*nod].a+arb[2*nod].b;
	else
		arb[nod].a=arb[2*nod+1].a+arb[2*nod+1].b;
}
void solve()
{
	//Ox=1
	int i,j,y,x,act;
	F[1]=n;
	for (i=2; i<=t; i++)
	{
		F[i]=F[i-1];
		for (j=0; j<E[i-1].size(); j++)
		{
			x=E[i][j];
			if (x!=1)
				F[i]--;
		}
	}
	cstr(1,t,1);
	for (i=1; i<=t; i++)
		update1(init[i],F[i]);
	rez=F[t];	
	for (i=2; i<=r; i++)
	{
		for (j=0; j<D[i].size(); j++)
		{
			y=D[i][j];
			a=y+1; b=t; value=1;
			if (a<=b)
				update2(1,t,1);
		}
		
		for (j=0; j<D[i-1].size(); j++)
		{
			y=D[i-1][j];
			a=1; b=y-1; value=-1;
			if (a<=b)
				update2(1,t,1);
		}
		
		act=arb[1].a+arb[1].b;
		rez=max(rez,act);
	}
}
int main()
{
	freopen("cadrane.in","r",stdin);
	freopen("cadrane.out","w",stdout);
	read();
	normalizare();
	solve();
	printf("%d\n",rez);
	return 0;
}