#include <bits/stdc++.h>
#define MAXN 100001
#define CHUNK ((int)sqrt(MAXN)+1)
using namespace std;
int n,rCows,lCows;
pair< int ,int > cows[ MAXN] ;
map< int ,int > xmap,ymap;
int bitL[ MAXN] { } ,bitR[ MAXN] { } ;
void update( int * bit,int i,int v)
{
while ( i< MAXN)
{
bit[ i] + = v;
i+ = ( i& ( - i) ) ;
}
}
int query( int * bit,int i)
{
int sum= 0 ;
while ( i> 0 )
{
sum+ = bit[ i] ;
i- = ( i& ( - i) ) ;
}
return sum;
}
inline int getMin( int y)
{
int a= query( bitL,y) ,b= query( bitR,y) ;
return max( max( a,lCows- a) ,max( b,rCows- b) ) ;
}
int test( )
{
int val[ CHUNK+ 1 ] ;
for ( int i= 0 ; i<= CHUNK; i++ ) val[ i] = getMin( i* CHUNK) ;
int z= min_element( val,val+ CHUNK+ 1 ) - val;
z* = CHUNK;
int cur= 1e9 ;
for ( int i= max( z- CHUNK,0 ) ; i< min( MAXN,z+ CHUNK) ; i++ ) cur= min( cur,getMin( i) ) ;
return cur;
}
int main( )
{
ifstream fin( "balancing.in" ) ;
ofstream fout( "balancing.out" ) ;
fin >> n;
for ( int i= 0 ; i< n; i++ )
{
int x,y;
fin >> x >> y;
cows[ i] = { x,y} ;
xmap[ x] = 0 ;
ymap[ y] = 0 ;
}
int pos= 1 ;
for ( auto & i: xmap)
{
i.second = pos;
pos++ ;
}
pos= 1 ;
for ( auto & i: ymap)
{
i.second = pos;
pos++ ;
}
for ( int i= 0 ; i< n; i++ )
{
cows[ i] .first = xmap[ cows[ i] .first ] ;
cows[ i] .second = ymap[ cows[ i] .second ] ;
}
sort( cows,cows+ n) ;
for ( int i= 0 ; i< n; i++ ) update( bitR,cows[ i] .second ,1 ) ;
int cur= 1e9 ;
pos= 0 ;
rCows= n;
lCows= 0 ;
for ( int i= 0 ; i< n; i++ )
{
int j;
for ( j= i; j< n; j++ )
{
if ( cows[ i] .first ! = cows[ j] .first ) break ;
update( bitR,cows[ j] .second ,- 1 ) ;
update( bitL,cows[ j] .second ,1 ) ;
rCows-- ;
lCows++ ;
}
cur= min( cur,test( ) ) ;
i= j- 1 ;
}
fout << cur << "\n " ;
return 0 ;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgTUFYTiAxMDAwMDEKI2RlZmluZSBDSFVOSyAoKGludClzcXJ0KE1BWE4pKzEpCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBuLHJDb3dzLGxDb3dzOwpwYWlyPGludCxpbnQ+IGNvd3NbTUFYTl07Cm1hcDxpbnQsaW50PiB4bWFwLHltYXA7CmludCBiaXRMW01BWE5de30sYml0UltNQVhOXXt9Owp2b2lkIHVwZGF0ZShpbnQgKmJpdCxpbnQgaSxpbnQgdikKewogICAgd2hpbGUoaTxNQVhOKQogICAgewogICAgICAgIGJpdFtpXSs9djsKICAgICAgICBpKz0oaSYoLWkpKTsKICAgIH0KfQppbnQgcXVlcnkoaW50ICpiaXQsaW50IGkpCnsKICAgIGludCBzdW09MDsKICAgIHdoaWxlKGk+MCkKICAgIHsKICAgICAgICBzdW0rPWJpdFtpXTsKICAgICAgICBpLT0oaSYoLWkpKTsKICAgIH0KICAgIHJldHVybiBzdW07Cn0KaW5saW5lIGludCBnZXRNaW4oaW50IHkpCnsKICAgIGludCBhPXF1ZXJ5KGJpdEwseSksYj1xdWVyeShiaXRSLHkpOwogICAgcmV0dXJuIG1heChtYXgoYSxsQ293cy1hKSxtYXgoYixyQ293cy1iKSk7Cn0KaW50IHRlc3QoKQp7CiAgICBpbnQgdmFsW0NIVU5LKzFdOwogICAgZm9yKGludCBpPTA7aTw9Q0hVTks7aSsrKXZhbFtpXT1nZXRNaW4oaSpDSFVOSyk7CiAgICBpbnQgej1taW5fZWxlbWVudCh2YWwsdmFsK0NIVU5LKzEpLXZhbDsKICAgIHoqPUNIVU5LOwogICAgaW50IGN1cj0xZTk7CiAgICBmb3IoaW50IGk9bWF4KHotQ0hVTkssMCk7aTxtaW4oTUFYTix6K0NIVU5LKTtpKyspY3VyPW1pbihjdXIsZ2V0TWluKGkpKTsKICAgIHJldHVybiBjdXI7Cn0KaW50IG1haW4oKQp7CiAgICBpZnN0cmVhbSBmaW4oImJhbGFuY2luZy5pbiIpOwogICAgb2ZzdHJlYW0gZm91dCgiYmFsYW5jaW5nLm91dCIpOwogICAgZmluID4+IG47CiAgICBmb3IoaW50IGk9MDtpPG47aSsrKQogICAgewogICAgICAgIGludCB4LHk7CiAgICAgICAgZmluID4+IHggPj4geTsKICAgICAgICBjb3dzW2ldPXt4LHl9OwogICAgICAgIHhtYXBbeF09MDsKICAgICAgICB5bWFwW3ldPTA7CiAgICB9CiAgICBpbnQgcG9zPTE7CiAgICBmb3IoYXV0byAmaTp4bWFwKQogICAgewogICAgICAgIGkuc2Vjb25kPXBvczsKICAgICAgICBwb3MrKzsKICAgIH0KICAgIHBvcz0xOwogICAgZm9yKGF1dG8gJmk6eW1hcCkKICAgIHsKICAgICAgICBpLnNlY29uZD1wb3M7CiAgICAgICAgcG9zKys7CiAgICB9CiAgICBmb3IoaW50IGk9MDtpPG47aSsrKQogICAgewogICAgICAgIGNvd3NbaV0uZmlyc3Q9eG1hcFtjb3dzW2ldLmZpcnN0XTsKICAgICAgICBjb3dzW2ldLnNlY29uZD15bWFwW2Nvd3NbaV0uc2Vjb25kXTsKICAgIH0KICAgIHNvcnQoY293cyxjb3dzK24pOwogICAgZm9yKGludCBpPTA7aTxuO2krKyl1cGRhdGUoYml0Uixjb3dzW2ldLnNlY29uZCwxKTsKICAgIGludCBjdXI9MWU5OwogICAgcG9zPTA7CiAgICByQ293cz1uOwogICAgbENvd3M9MDsKICAgIGZvcihpbnQgaT0wO2k8bjtpKyspCiAgICB7CiAgICAgICAgaW50IGo7CiAgICAgICAgZm9yKGo9aTtqPG47aisrKQogICAgICAgIHsKICAgICAgICAgICAgaWYoY293c1tpXS5maXJzdCE9Y293c1tqXS5maXJzdClicmVhazsKICAgICAgICAgICAgdXBkYXRlKGJpdFIsY293c1tqXS5zZWNvbmQsLTEpOwogICAgICAgICAgICB1cGRhdGUoYml0TCxjb3dzW2pdLnNlY29uZCwxKTsKICAgICAgICAgICAgckNvd3MtLTsKICAgICAgICAgICAgbENvd3MrKzsKICAgICAgICB9CiAgICAgICAgY3VyPW1pbihjdXIsdGVzdCgpKTsKICAgICAgICBpPWotMTsKICAgIH0KICAgIGZvdXQgPDwgY3VyIDw8ICJcbiI7CiAgICByZXR1cm4gMDsKfQ==
compilation info
prog.cpp:8:15: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
int bitL[MAXN]{},bitR[MAXN]{};
^
prog.cpp:8:28: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
int bitL[MAXN]{},bitR[MAXN]{};
^
prog.cpp: In function 'int main()':
prog.cpp:51:21: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
cows[i]={x,y};
^
prog.cpp:51:16: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
cows[i]={x,y};
^
prog.cpp:56:15: error: ISO C++ forbids declaration of 'i' with no type [-fpermissive]
for(auto &i:xmap)
^
prog.cpp:56:17: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
for(auto &i:xmap)
^
prog.cpp:58:11: error: request for member 'second' in 'i', which is of non-class type 'int'
i.second=pos;
^
prog.cpp:62:15: error: ISO C++ forbids declaration of 'i' with no type [-fpermissive]
for(auto &i:ymap)
^
prog.cpp:62:17: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
for(auto &i:ymap)
^
prog.cpp:64:11: error: request for member 'second' in 'i', which is of non-class type 'int'
i.second=pos;
^
stdout