Cod sursa(job #754254)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 1 iunie 2012 11:04:29
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include<stdio.h>
#include<algorithm>

#define maxn 100005

using namespace std;

FILE*f=fopen("cadrane.in","r");
FILE*g=fopen("cadrane.out","w");

int n,a,b;
int V[maxn],O[maxn],v2,o2,v,o;
int start[maxn];

struct pct{
	int x,y;
}A[maxn];

struct _arb{
	int ad;
	int min;
}Arb[4*maxn];

inline int cb ( int val , int *V , int N ){
	int p = 1,m,u = N;
	
	while ( p <= u ){
		m = (p+u)>>1;
		if ( V[m] == val )	return m;
		if ( V[m] > val )	u = m - 1;
		else	p = m + 1;
	}
	
	return 0;
}

inline void normalizare () {
	
	sort(V+1,V+v2+1);
	sort(O+1,O+o2+1);
	
	for ( int i = 1 ; i <= v2 ; ++i ){
		if ( i == 1 || V[i] != V[i-1] ){
			V[++v] = V[i];
		}
	}
	for ( int i = 1 ; i <= o2 ; ++i ){
		if ( i == 1 || O[i] != O[i-1] ){
			O[++o] = O[i];
		}
	}
	
	for ( int i = 1 ; i <= n ; ++i ){
		A[i].x = cb(A[i].x,V,v);
		A[i].y = cb(A[i].y,O,o);
	}
}

struct cmp1{
	inline bool operator () ( const pct &a , const pct &b ){
		return a.y < b.y;
	}
};

void init ( int nod , int st , int dr ){
	
	if ( st == dr ){
		Arb[nod].min = start[st];
		return ;
	}
	
	int mij = (st + dr)>>1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	
	init(nodst,st,mij);
	init(noddr,mij+1,dr);
	
	Arb[nod].min = min(Arb[nodst].min,Arb[noddr].min);
}

void update ( int nod , int st , int dr , int val ){
	
	if ( a <= st && dr <= b ){
		Arb[nod].ad += val;
		return ;
	}
	
	int mij = (st + dr)>>1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	
	Arb[nodst].ad += Arb[nod].ad;
	Arb[noddr].ad += Arb[nod].ad;
	Arb[nod].min += Arb[nod].ad; Arb[nod].ad = 0;
	
	if ( a <= mij ){
		update(nodst,st,mij,val);
	}
	if ( b > mij ){
		update(noddr,mij+1,dr,val);
	}
	
	Arb[nod].min = min(Arb[nodst].min+Arb[nodst].ad,Arb[noddr].min+Arb[noddr].ad);
}

struct cmp2{
	inline bool operator () ( const pct &a , const pct &b ){
		return a.x < b.x;
	}
};

int main () {
	
	fscanf(f,"%d",&n);
	for ( int i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d %d",&A[i].x,&A[i].y);
		V[++v2] = A[i].x; O[++o2] = A[i].y;
	}
	
	normalizare();
	
	sort(A+1,A+n+1,cmp1());
	
	int p = n+1;
	for ( int i = o ; i >= 1 ; --i ){
		while ( p > 1 && A[p-1].y >= i ){
			--p;
		}
		start[i] = n-p+1;
	}
	
	init(1,1,o);
	
	sort(A+1,A+n+1,cmp2());
	
	int st=0,dr=0,sol=0;
	for ( int i = 1 ; i <= v ; ++i ){
		st = dr+1;
		while ( A[dr+1].x == i ){
			++dr;
		}
		
		for ( int j = st ; j <= dr ; ++j ){
			a = A[j].y+1; b = o;
			if ( a <= b ){
				update(1,1,o,1);
			}
		}
		
		sol = max(sol,Arb[1].min+Arb[1].ad);
		
		for ( int j = st ; j <= dr ; ++j ){
			a = 1; b = A[j].y-1;
			if ( a <= b ){
				update(1,1,o,-1);
			}
		}
	}
	
	fprintf(g,"%d\n",sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}