Cod sursa(job #1955499)

Utilizator Andrei501Clicinschi Andrei Andrei501 Data 6 aprilie 2017 00:36:54
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>

using namespace std;

struct pachet
{
    int x,y;
};

vector <pachet> v[5];
int c[50001];

int caut (int s,int l)
{
    int L=floor(log2(l));
    int pas=1<<L,j=0;
    while (pas!=0)
    {
        if (j+pas<=l&&c[j+pas]>=s) //u->c
        {
            j+=pas;
        }
        pas>>=1;
    }
    return j+1;
}

bool comp (pachet A,pachet B)
{
    return A.x<B.x;
}

int main()
{
    freopen ("pachete.in","r",stdin);
    freopen ("pachete.out","w",stdout);

    int N,X,Y;
    scanf ("%d",&N);
    scanf ("%d %d",&X,&Y);

    int i,ii;
    pachet a;
    for (i=1; i<=N; i++)
    {
        scanf ("%d %d",&a.x,&a.y);
        if (a.x>=X&&a.y>=Y)
        {
            v[1].push_back(a);
        }
        else if (a.x<X&&a.y>Y)
        {
            v[2].push_back(a);
        }
        else if (a.x<X&&a.y<Y)
        {
            v[3].push_back(a);
        }
        else if (a.x>X&&a.y<Y)
        {
            v[4].push_back(a);
        }
    }

    for (ii=1; ii<=4; ii++)
    {
        sort (v[ii].begin(),v[ii].end(),comp);
    }

    int nr=0,C,c1;

    for (ii=1; ii<=4; ii++)
    {
        c1=1;
        c[c1]=-2000000001;
        for (i=0; i<v[ii].size(); i++)
        {
            if (c1==1&&c[c1]==-2000000001)
            {
                c[c1]=v[ii][i].y;
                nr++;
            }
            else
            {
                C=caut(v[ii][i].y,c1);
                if (C>c1)
                {
                    c[++c1]=v[ii][i].y;
                    nr++;
                }
                else
                {
                    c[C]=v[ii][i].y;
                }
            }
        }
    }

    printf ("%d\n",nr);

    return 0;
}