Cod sursa(job #1306059)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 30 decembrie 2014 14:47:07
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include<fstream>
#include<algorithm>
using namespace std;
int n, i, nr, x, y, j, ii, jj, w[4], p, u, mid, nr1;
int s[50001];
pair<int, int> v[4][50001];
ifstream fin("pachete.in");
ofstream fout("pachete.out");
int main(){
	fin>> n >> x >> y;
	for(i = 1; i <= n; i++){
		fin>> ii >> jj;
		if(ii >= x){
			if(jj > y){
				w[0]++;
				v[0][w[0]].first = ii;
				v[0][w[0]].second = jj;
			}
			else{
				w[1]++;
				v[1][w[1]].first = ii;
				v[1][w[1]].second = jj;
			}
		}
		else{
			if(jj <= y){
				w[2]++;
				v[2][w[2]].first = ii;
				v[2][w[2]].second = jj;
			}
			else{
				w[3]++;
				v[3][w[3]].first = ii;
				v[3][w[3]].second = jj; 
			}
		}
	}
	sort(v[0] + 1, v[0] + w[0] + 1);
	if(w[0] != 0){
		nr1 = 1;
		s[1] = v[0][1].second;
		for(i = 2; i <= w[0]; i++){
			p = 1;
			u = nr1;
			while(p <= u){
				mid = (p + u) / 2;
				if(v[0][i].second < s[mid]){
					p = mid + 1;
				}
				else{
					u = mid - 1;
				}
			}
			if(p == nr1 + 1){
				nr1++;
				s[nr1] = v[0][i].second;
			}
			else{
				s[p] = v[0][i].second;
			}
		}
		nr += nr1;
	}
	sort(v[1] + 1, v[1] + w[1] + 1);
	if(w[1] != 0){
		nr1 = 1;
		s[1] = v[1][1].second;
		for(i = 2; i <= w[1]; i++){
			p = 1;
			u = nr1;
			while(p <= u){
				mid = (p + u) / 2;
				if(v[1][i].second > s[mid]){
					p = mid + 1;
				}
				else{
					u = mid - 1;
				}
			}
			if(p == nr1 + 1){
				nr1++;
				s[nr1] = v[1][i].second;
			}
			else{
				s[p] = v[1][i].second;
			}
		}
		nr += nr1;
	}
	sort(v[2] + 1, v[2] + w[2] + 1);
	if(w[2] != 0){
		nr1 = 1;
		s[1] = v[2][w[2]].second;
		for(i = w[2] - 1; i >= 1; i--){
			p = 1;
			u = nr1;
			while(p <= u){
				mid = (p + u) / 2;
				if(v[2][i].second > s[mid]){
					p = mid + 1;
				}
				else{
					u = mid - 1;
				}
			}
			if(p == nr1 + 1){
				nr1++;
				s[nr1] = v[2][i].second;
			}
			else{
				s[p] = v[2][i].second;
			}
		}
		nr += nr1;
	}
	sort(v[3] + 1, v[3] + w[3] + 1);
	if(w[3] != 0){
		nr1 = 1;
		s[1] = v[3][w[3]].second;
		for(i = w[3] - 1; i >= 1; i--){
			p = 1;
			u = nr1;
			while(p <= u){
				mid = (p + u) / 2;
				if(v[3][i].second < s[mid]){
					p = mid + 1;
				}
				else{
					u = mid - 1;
				}
			}
			if(p == nr1 + 1){
				nr1++;
				s[nr1] = v[3][i].second;
			}
			else{
				s[p] = v[3][i].second;
			}
		}
		nr += nr1;
	}
	fout<< nr;
	return 0;
}