Cod sursa(job #467775)

Utilizator AndreyPAndrei Poenaru AndreyP Data 30 iunie 2010 15:15:25
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define N 100010
typedef pair< int,int > pii;

int n;
pii a[N];
pii t[262510];
int poz,val;
int h[N];

inline void citire()
{
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d%d",&a[i].fs,&a[i].sc);
        h[++h[0]]=a[i].sc;
    }

    sort(a+1,a+n+1);
    sort(h+1,h+h[0]+1);
    int cnt=1;
    for(int i=2; i<=h[0]; ++i)
    {
        if(h[i]!=h[cnt])
            h[++cnt]=h[i];
    }
    h[0]=cnt;
}

inline int hash(int x)
{
    int p=1,u=h[0];
    if(h[1]==x)
        return 1;
    if(h[u]==x)
        return u;

    int m;
    while(p<u)
    {
        m=(p+u)>>1;
        if(x<=h[m])
            u=m;
        else
            p=m+1;
    }
    return p;
}

inline int minim(int x,int y)
{
    return ( (x<y) ? (x) : (y) );
}

void update(int p,int u,int i)
{
    if(poz<p || poz> u)
        return;
    if(p>u)
        return;
    if(p==u)
    {
        t[i].fs+=val;
        t[i].sc=t[i].fs;
        return;
    }

    int m=(p+u)>>1;
    if(poz<=m)
        update(p,m,i<<1);
    else
        update(m+1,u,(i<<1)+1);

    t[i].fs=t[i<<1].fs+t[(i<<1)+1].fs;
    t[i].sc=minim(t[i<<1].sc,t[i<<1].fs+t[(i<<1)+1].sc);
}

inline void rezolva()
{
    val=-1;
    for(int i=1; i<=n; ++i)
    {
        a[i].sc=hash(a[i].sc);
        poz=a[i].sc+1;
        update(1,n,1);
    }

    int nrd=n;
    int i=1,j=1;
    int rez=0;
    while(i<=n)
    {
        val=1;
        for(; j<=n && a[j].fs==a[i].fs; ++j)
        {
            poz=a[j].sc+1;
            update(1,n,1);
        }

        if(nrd+t[1].sc>rez)
            rez=nrd+t[1].sc;

        nrd-=j-i;
        for(int t=i; t<j; ++t)
        {
           poz=a[t].sc;
           update(1,n,1);
        }
        i=j;
    }

    printf("%d\n",rez);
}

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

    citire();
    rezolva();

    return 0;
}