Cod sursa(job #2113377)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 24 ianuarie 2018 15:29:40
Problema Pachete Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <fstream>
#include <algorithm>
#include <iostream>
#include <cstring>
#define MAX_VAL 50005
#define INPUT  "pachete.in"
#define OUTPUT "pachete.out"
using namespace std;

ifstream f (INPUT );
ofstream g (OUTPUT);

int n, X, Y, x, y, yMaxA, yMaxB, maxA, maxB, Sol[MAX_VAL], ans;

struct str{
	int x, y;
}a1[MAX_VAL], b1[MAX_VAL], a2[MAX_VAL], b2[MAX_VAL];

bool cmp( str a, str b ){
	return a.x > b.x;
}

int binSearch(int lt, int rt, int val){
    int mid;
    while( lt <= rt ){
        mid = (lt+rt)/2;
        if( Sol[mid-1] > val && val >= Sol[mid] )
            return mid;
        else if( Sol[mid] < val )
            rt = mid - 1;
        else
            lt = mid + 1;
    }
    return lt;
}


int main(){
	f >> n;
	f >> X >> Y;
	for(int i = 1; i <= n; i++){
		f >> x >> y;
		if( y > Y ){
			if( x < X ){
				a1[++a1[0].x].x = x;
				a1[a1[0].x].y   = y;
			}
			else{
				a2[++a2[0].x].x = x;
				a2[a2[0].x].y   = y;
			}
 		}

		else{
			if( x < X ){
				b1[++b1[0].x].x = x;
				b1[b1[0].x].y   = y;
			}
			else{
				b2[++b2[0].x].x = x;
				b2[b2[0].x].y   = y;
			}
		}
	}

	sort( a1+1, a1+a1[0].x+1, cmp);
	sort( a2+1, a2+a2[0].x+1, cmp);
	sort( b1+1, b1+b1[0].x+1, cmp);
	sort( b2+1, b2+b2[0].x+1, cmp);
	int nr = 0, poz = 0;
	Sol[0] = 1000000000;
    for(int i = 1; i <= a1[0].x; i++){
        poz = binSearch(1, nr+1, a1[i].y);
        if(poz == nr+1)
            nr++;
        Sol[poz] = a1[i].y;
    }
    ans += nr;
    nr = 0;
    memset(Sol, 0, sizeof(Sol));
    Sol[0] = 1000000000;
    for(int i = 1; i <= a2[0].x; i++){
        poz = binSearch(1, nr+1, a2[i].y);
        if(poz == nr+1)
            nr++;
        Sol[poz] = a2[i].y;
    }
    ans += nr;
    nr = 0;
    memset(Sol, 0, sizeof(Sol));
    Sol[0] = 1000000000;
    for(int i = 1; i <= b1[0].x; i++){
        poz = binSearch(1, nr+1, b1[i].y);
        if(poz == nr+1)
            nr++;
        Sol[poz] = b1[i].y;
    }

    ans += nr;
    nr = 0;
    memset(Sol, 0, sizeof(Sol));
    Sol[0] = 1000000000;
    for(int i = 1; i <= b2[0].x; i++){
        poz = binSearch(1, nr+1, b2[i].y);
        if(poz == nr+1)
            nr++;
        Sol[poz] = b2[i].y;
    }
    ans += nr;
	g << ans << '\n';
	f.close();
	g.close();
	return 0;
}