Cod sursa(job #1305976)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 30 decembrie 2014 13:38:32
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 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; 
			}
		}
	}
	for(j = 0; j < 4; j++){
		sort(v[j] + 1, v[j] + w[j] + 1);
		if(w[j] != 0){
			nr1 = 1;
			s[1] = v[j][1].second;
			for(i = 2; i <= w[j]; i++){
				p = 1;
				u = nr1;
				while(p <= u){
					mid = (p + u) / 2;
					if(v[j][i].second < s[mid]){
						p = mid + 1;
					}
					else{
						u = mid - 1;
					}
				}
				if(p == nr1 + 1){
					nr1++;
					s[nr1] = v[j][i].second;
				}
				else{
					s[p] = v[j][i].second;
				}
			}
			nr += nr1;
		}
	}
	fout<< nr;
	return 0;
}