Pagini recente » Cod sursa (job #2688454) | Cod sursa (job #2131599) | Cod sursa (job #1820982) | Cod sursa (job #456193) | Cod sursa (job #467775)
Cod sursa(job #467775)
#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;
}