fork download

copy

#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;
}

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;
           ^

Standard output is empty