Cod sursa(job #467455)

Utilizator katakunaCazacu Alexandru katakuna Data 28 iunie 2010 23:36:01
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define Nmax 100010
#define MOD 100013

struct punct {int x, y;} v[Nmax];
int n, i, N, sol, A, B, val, INF;
int Y[Nmax], x[Nmax], X[Nmax];
vector < pair <int, int> > Hp[MOD + 10], Hn[MOD + 10];
vector < pair <int, int> >::iterator it;
int AI[4 * Nmax], AD[4 * Nmax];

void add_hash (int val) {
	N++;
	if (val >= 0) Hp[val % MOD].push_back ( make_pair (val, N) );
	else {
		val = -val;
		Hn[val % MOD].push_back ( make_pair (val, N) );
	}
} 

int query_hash (int val) {
	
	if (val >= 0) {
		int nod = val % MOD;
		for (it = Hp[nod].begin (); it != Hp[nod].end (); it++) {
			if (it->first == val) return it->second;
		}
	}
	else {
		val = -val;
		int nod = val % MOD;
		for (it = Hn[nod].begin (); it != Hn[nod].end (); it++) {
			if (it->first == val) return it->second;
		}
	}
	
	return 0;
}

int cmp (int x, int y) {
	return x > y;
}

int cmp2 (const punct &a,const punct &b) {
	return a.x < b.x;
}

void citire () {

	scanf ("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf ("%d %d", &v[i].x, &v[i].y);
		Y[i] = v[i].y;
		x[i] = v[i].x;
	}
	
	sort (Y + 1, Y + n + 1, cmp);
	sort (x + 1, x + n + 1);
	sort (v + 1, v + n + 1, cmp2);
	
	for (i = 1; i <= n; i++) {
		if (i == 1 || Y[i] != Y[i-1])
			add_hash (Y[i]);
		if (i == 1 || x[i] != x[i-1])
			X[++X[0]] = x[i];
	}
}

#define MIJ ((st + dr) >> 1)
#define N1 (nod << 1)
#define N2 ((nod << 1) + 1)

void update_AI (int nod, int st, int dr) {
	
	if (A <= st && dr <= B) {
		AD[nod]+= val;
		return ;
	}
	
	if (AD[nod] != 0) {
		AI[nod]+= AD[nod];
		AD[N1]+= AD[nod];
		AD[N2]+= AD[nod];
		AD[nod] = 0;
	}
	
	if (A <= MIJ) update_AI (N1, st, MIJ);
	if (MIJ < B) update_AI (N2, MIJ + 1, dr);
	
	AI[nod] = min (AI[N1] + AD[N1], AI[N2] + AD[N2]);
} 

void rezolva () {
	
	int poz, NN = 4 * N + 1; INF = 1 << 30;
	
	for (i = 1; i <= n; i++) {
		poz = query_hash (v[i].y);
		A = poz; B = N; val = 1;
		update_AI (1, 1, N);
	}
	
	int p, j;
	
	p = 1;
	for (i = 1; i <= X[0]; i++) {
		while (p <= n && v[p].x < X[i]) {
			poz = query_hash (v[p].y);
			A = poz + 1; B = N; val = -1;
			if (A <= B) update_AI (1, 1, N);
			A = 1; B = poz - 1; val = 1;
			if (A <= B) update_AI (1, 1, N);
			p++;
		}
		
		for (j = p; j <= n && v[j].x == X[i]; j++) {
			poz = query_hash (v[j].y);
			A = 1; B = poz - 1; val = 1;
			if (A <= B) update_AI (1, 1, N);
		}
		
		sol = max (sol, AI[1] + AD[1]);
		
		for (j = p; j <= n && v[j].x == X[i]; j++) {
			poz = query_hash (v[j].y);
			A = poz + 1; B = N; val = -1;
			if (A <= B) update_AI (1, 1, N);
			p++;
		}
	}
}

int main () {
	
	freopen ("cadrane.in", "r", stdin);
	freopen ("cadrane.out", "w", stdout);
	
	citire ();
	rezolva ();
	
	printf ("%d", sol);
	
	return 0;
}