Cod sursa(job #1949032)

Utilizator UrsuDanUrsu Dan UrsuDan Data 1 aprilie 2017 17:36:49
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct puncte
{
    int x,y;
};
puncte v[50010];

int up[50010];
int down[50010];

bool cmp(puncte a,puncte b)
{
    return a.x<b.x;
}

int main()
{
    freopen("pachete.in","r",stdin);
    freopen("pachete.out","w",stdout);
    int n,x,y,k1=0,k2=0,ans=0,i,answer,bit,start=0,rtup,rt;
    scanf("%d%d%d",&n,&x,&y);
    for(i=1; i<=n; i++)
        scanf("%d%d",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp);
    start=0;
    for(bit=15; bit>=0; bit--)
        if(start+(1<<bit)<=n && x>v[start+(1<<bit)].x)
            start+=(1<<bit);
    up[0]=2000000010;
    down[0]=-up[0];
    for(i=start+1; i<=n; i++)
    {
        if(v[i].y>=y)
        {
            answer=0;
            for(bit=15; bit>=0; bit--)
                if(answer+(1<<bit)<=k1 && v[i].y<up[answer+(1<<bit)])
                    answer+=(1<<bit);
            answer++;
            if(answer>k1)
            {
                k1++;
                up[k1]=v[i].y;
            }
            else
                up[answer]=v[i].y;
        }
        else
        {
            answer=0;
            for(bit=15; bit>=0; bit--)
                if(answer+(1<<bit)<=k2 && v[i].y>down[answer+(1<<bit)])
                    answer+=(1<<bit);
            answer++;
            if(answer>k2)
            {
                k2++;
                down[k2]=v[i].y;
                if(up[k1]==y)
                    k1--;
            }
            else
                down[answer]=v[i].y;
        }
    }
    ans=k1+k2;
    k1=0;
    k2=0;
    for(i=start;i>=1;i--)
    {
        if(v[i].y>=y)
        {
            answer=0;
            for(bit=15; bit>=0; bit--)
                if(answer+(1<<bit)<=k1 && v[i].y<up[answer+(1<<bit)])
                    answer+=(1<<bit);
            answer++;
            if(answer>k1)
            {
                k1++;
                up[k1]=v[i].y;
            }
            else
                up[answer]=v[i].y;
        }
        else
        {
            answer=0;
            for(bit=15; bit>=0; bit--)
                if(answer+(1<<bit)<=k2 && v[i].y>down[answer+(1<<bit)])
                    answer+=(1<<bit);
            answer++;
            if(answer>k2)
            {
                k2++;
                down[k2]=v[i].y;
                if(up[k1]==y)
                    k1--;
            }
            else
                down[answer]=v[i].y;
        }
    }
    ans+=k1;
    ans+=k2;
    printf("%d",ans);
    return 0;
}