Cod sursa(job #2113931)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 25 ianuarie 2018 11:42:58
Problema Pachete Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 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;
}

bool cmp1( 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 binSearch1(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, cmp1);
    sort( a2+1, a2+a2[0].x+1, cmp);
    sort( b1+1, b1+b1[0].x+1, cmp1);
    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;
    for(int i = 1; i <= nr; i++)
        Sol[i] = 1000000000;
    nr = 0;
    Sol[0] = -1000000000;
    Sol[1] = 1000000000;
    for(int i = 1; i <= b1[0].x; i++){
        poz = binSearch1(1, nr+1, b1[i].y);
        if(poz >= nr+1)
            nr++;
        Sol[poz] = b1[i].y;
    }

    ans += nr;
    Sol[0] = -1000000000;
    for(int i = 1; i <= nr; i++)
        Sol[i] = 1000000000;
    nr = 0;
    for(int i = 1; i <= b2[0].x; i++){
        poz = binSearch1(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;
}