Cod sursa(job #847222)

Utilizator stoicatheoFlirk Navok stoicatheo Data 3 ianuarie 2013 16:34:13
Problema Cadrane Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include<fstream>
#include<algorithm>
 
using namespace std;
 
const char iname[]="cadrane.in";
const char oname[]="cadrane.out";
const int maxn=300005;
 
ifstream f(iname);
ofstream g(oname);
 
class point
{
    public:
    int x,y,z;
} a[maxn];
 
bool operator<(const point& a,const point& b)
{
    return a.x<b.x;
}
 
class fcomp
{
    public:
    bool operator()(const point& a,const point &b)
    {
        return a.y<b.y;
    }
};
 
int n,i,j,arb[maxn][2],maxt,k,updatearb[maxn];
 
void update(int nod,int left,int right,int start,int finish,int val)
{
    if(start<=left&&right<=finish)
    {
        arb[nod][0]+=val;
        return;
    }
    arb[nod*2][0]+=arb[nod][0];
    arb[nod*2+1][0]+=arb[nod][0];
    arb[nod][0]=0;
    int mid=(left+right)>>1;
    if(start<=mid)
        update(nod*2,left,mid,start,finish,val);
    if(mid<finish)
        update(nod*2+1,mid+1,right,start,finish,val);
    arb[nod][1]=min(arb[nod*2][0]+arb[nod*2][1],arb[nod*2+1][0]+arb[nod*2+1][1]);
}
 
int query()
{
    return arb[1][0]+arb[1][1];
}
 
void build_arb(int nod,int left,int right)
{
    if(left==right)
    {
        arb[nod][1]=updatearb[left];
        return;
    }
    int mid=(left+right)>>1;
    build_arb(nod*2,left,mid);
    build_arb(nod*2+1,mid+1,right);
    arb[nod][1]=min(arb[nod*2][1],arb[nod*2+1][1]);
}
 
int main()
{
    f>>n;
    for(i=1;i<=n;++i)
        f>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,fcomp());
    a[1].z=1;
    updatearb[1]=n;
    for(i=2;i<=n;++i)
    {
        a[i].z=a[i-1].z+(int)(a[i].y!=a[i-1].y);
        if(a[i].y!=a[i-1].y)
            updatearb[a[i].z]=n-i+1;
    }
    k=a[n].z;
    build_arb(1,1,k);
    sort(a+1,a+n+1);
    fprintf(stderr,"%d",query());
    for(i=1;i<=n;i=j+1)
    {
        for(j=i;j<n&&a[j+1].x==a[i].x;++j)
            update(1,1,k,a[j].z,k,1);
        update(1,1,k,a[j].z,k,1);
        maxt=max(maxt,query());
        for(j=i;j<n&&a[j+1].x==a[i].x;++j)
            update(1,1,k,1,a[j].z,-1);
        update(1,1,k,1,a[j].z,-1);
    }
 
    g<<maxt<<"\n";
}