Cod sursa(job #480126)

Utilizator DraStiKDragos Oprica DraStiK Data 26 august 2010 14:57:28
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <algorithm>
using namespace std;

#define DIM 100005
#define sc second
#define fs first

pair <int,int> v[DIM],aint[DIM<<2];
int n,m,sol;
int h[DIM];

void read ()
{
    int i;

    scanf ("%d",&n);
    for (i=1; i<=n; ++i)
    {
        scanf ("%d%d",&v[i].fs,&v[i].sc);
        h[++m]=v[i].sc;
    }
}

void update (int nod,int st,int dr,int poz,int val)
{
    int mij;

    if (st==dr)
    {
        aint[nod].fs+=val;
        aint[nod].sc=aint[nod].fs;
    }
    else
    {
        mij=(st+dr)/2;
        if (poz<=mij)
            update (nod<<1,st,mij,poz,val);
        else
            update ((nod<<1)|1,mij+1,dr,poz,val);
        aint[nod].fs=aint[nod<<1].fs+aint[(nod<<1)|1].fs;
        aint[nod].sc=min (aint[nod<<1].sc,aint[nod<<1].fs+aint[(nod<<1)|1].sc);
    }
}

void init ()
{
    int i,j;

    sort (v+1,v+n+1);
    sort (h+1,h+m+1);
    for (i=1, j=2; j<=m; ++j)
        if (h[i]!=h[j])
            h[++i]=h[j];
    m=i;
    for (i=1; i<=n; ++i)
    {
        v[i].sc=lower_bound (h+1,h+m+1,v[i].sc)-h;
        update (1,1,n,v[i].sc+1,-1);
    }
}

void solve ()
{
    int i,j,k,nrc;

    nrc=n;
    for (i=j=1; i<=n; i=j)
    {
        for ( ; j<=n && v[i].fs==v[j].fs; ++j)
            update (1,1,n,v[j].sc+1,1);
        sol=max (sol,nrc+aint[1].sc);
        nrc-=j-i;
        for (k=i; k<j; ++k)
            update (1,1,n,v[k].sc,1);
    }
    printf ("%d",sol);
}

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

    read ();
    init ();
    solve ();

    return 0;
}