Pagini recente » Cod sursa (job #1316891) | Cod sursa (job #1969672) | Cod sursa (job #2527450) | Cod sursa (job #2460341) | Cod sursa (job #957713)
Cod sursa(job #957713)
#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;
}