Cod sursa(job #957713)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 5 iunie 2013 20:19:19
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.24 kb
#include <fstream>
#include <algorithm>

using namespace std;

#define marime 262144

int n;

ifstream cin("cadrane.in");
ofstream cout("cadrane.out");

struct nod
{
    int st,dr;
    int sum_s;
    int sum_j;
    int best;
}arb[marime];

struct punct
{
    int x,y;
}v[100005];

bool operator<(const punct &a,const punct &b)
{
    if(a.y>b.y)
        return 1;
    else if(a.y==b.y)
    {
        if(a.x<b.x)
           return 1;
    }
    return 0;
}
/////////////////////
struct aux
{
    int val;
    int ind;
}x[100005],y[100005];

bool operator<(const aux &a,const aux &b)
{
    if(a.val<b.val)
        return 1;
    return 0;
}

#define inf 10000000 //de mod

int minim(int a,int b)
{
    if(a<b)
        return a;
    return b;
}

void calc_best(nod &a,nod b,nod c)
{
    int v1=b.best+c.sum_s;
    int v2=c.best+b.sum_j;
    a.best=minim(v1,v2);
}

void build(int st,int dr,int poz)
{
    //cout<<"build("<<st<<","<<dr<<","<<poz<<")"<<endl;
    arb[poz].st=st;
    arb[poz].dr=dr;
    arb[poz].best=0;  //discutabil
    arb[poz].sum_s=0;
    arb[poz].sum_j=0;
    //arb[poz].result=0;

    if(st==dr)
        return;
    int mijl=(st+dr)>>1;
    build(st,mijl,poz<<1);
    build(mijl+1,dr,(poz<<1)+1);
}

void update(int unde,bool sus,int val,int poz)
{
    if(arb[poz].st==arb[poz].dr && arb[poz].st==unde)
    {
        if(sus)
            arb[poz].sum_s+=val;
        else
            arb[poz].sum_j+=val;
        arb[poz].best=arb[poz].sum_s+arb[poz].sum_j;
        return;
    }

    int mijl=(arb[poz].st+arb[poz].dr)>>1;
    if(unde<=mijl)
        update(unde,sus,val,poz<<1);
    else
        update(unde,sus,val,(poz<<1)+1);
    if(sus)
        arb[poz].sum_s+=val;
    else
        arb[poz].sum_j+=val;
    calc_best(arb[poz],arb[poz<<1],arb[(poz<<1)+1]);
}

int main()
{
    int i;

    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>v[i].y>>v[i].x;
        y[i].val=v[i].y;
        y[i].ind=i;
        x[i].val=v[i].x;
        x[i].ind=i;
    }

    sort(y+1,y+n+1);
    sort(x+1,x+n+1);
    int cat1=1;
    int cat2=1;

    int maxim=-1;

    v[y[1].ind].y=1;
    v[x[1].ind].x=1;
    x[0]=x[1];
    y[0]=y[1];

    for(i=1;i<=n;i++)
    {
       if(y[i].val!=y[i-1].val)
          cat2++;
       if(x[i].val!=x[i-1].val)
          cat1++;
       v[y[i].ind].y=cat2;
       v[x[i].ind].x=cat1;
    }
    sort(v+1,v+n+1);
        build(1,n,1);
    //Acum coordonatele punctelor sunt normalizate si sortate deci putem incepe baleerea
    for(i=1;i<=n;i++)
    {
        //cout<<v[i].y<<' '<<v[i].x<<endl;
        update(v[i].x,0,1,1);
    }

   // v[0].x=v[1].x;
   // v[0].y=v[1].y;
    int retin[100005];
    int j=0;
    i=1;

    while(i<=n)
    {
        j=0;
        do
        {
            update(v[i].x,1,1,1);
            retin[j++]=i;
            i++;
            if(i>n)
              break;
        }
        while(v[i].y==v[i-1].y);

        //cout<<"best la i="<<i<<" este "<<arb[1].best<<endl;
        if(arb[1].best>maxim)
            maxim=arb[1].best;

        while(j>0)
            update(v[retin[--j]].x,0,-1,1);
    }
    cout<<maxim<<'\n';
    cin.close();
    cout.close();
    return 0;
}