fork download
  1. #include <bits/stdc++.h>
  2. #define MAXN 100001
  3. #define CHUNK ((int)sqrt(MAXN)+1)
  4. using namespace std;
  5. int n,rCows,lCows;
  6. pair<int,int> cows[MAXN];
  7. map<int,int> xmap,ymap;
  8. int bitL[MAXN]{},bitR[MAXN]{};
  9. void update(int *bit,int i,int v)
  10. {
  11. while(i<MAXN)
  12. {
  13. bit[i]+=v;
  14. i+=(i&(-i));
  15. }
  16. }
  17. int query(int *bit,int i)
  18. {
  19. int sum=0;
  20. while(i>0)
  21. {
  22. sum+=bit[i];
  23. i-=(i&(-i));
  24. }
  25. return sum;
  26. }
  27. inline int getMin(int y)
  28. {
  29. int a=query(bitL,y),b=query(bitR,y);
  30. return max(max(a,lCows-a),max(b,rCows-b));
  31. }
  32. int test()
  33. {
  34. int val[CHUNK+1];
  35. for(int i=0;i<=CHUNK;i++)val[i]=getMin(i*CHUNK);
  36. int z=min_element(val,val+CHUNK+1)-val;
  37. z*=CHUNK;
  38. int cur=1e9;
  39. for(int i=max(z-CHUNK,0);i<min(MAXN,z+CHUNK);i++)cur=min(cur,getMin(i));
  40. return cur;
  41. }
  42. int main()
  43. {
  44. ifstream fin("balancing.in");
  45. ofstream fout("balancing.out");
  46. fin >> n;
  47. for(int i=0;i<n;i++)
  48. {
  49. int x,y;
  50. fin >> x >> y;
  51. cows[i]={x,y};
  52. xmap[x]=0;
  53. ymap[y]=0;
  54. }
  55. int pos=1;
  56. for(auto &i:xmap)
  57. {
  58. i.second=pos;
  59. pos++;
  60. }
  61. pos=1;
  62. for(auto &i:ymap)
  63. {
  64. i.second=pos;
  65. pos++;
  66. }
  67. for(int i=0;i<n;i++)
  68. {
  69. cows[i].first=xmap[cows[i].first];
  70. cows[i].second=ymap[cows[i].second];
  71. }
  72. sort(cows,cows+n);
  73. for(int i=0;i<n;i++)update(bitR,cows[i].second,1);
  74. int cur=1e9;
  75. pos=0;
  76. rCows=n;
  77. lCows=0;
  78. for(int i=0;i<n;i++)
  79. {
  80. int j;
  81. for(j=i;j<n;j++)
  82. {
  83. if(cows[i].first!=cows[j].first)break;
  84. update(bitR,cows[j].second,-1);
  85. update(bitL,cows[j].second,1);
  86. rCows--;
  87. lCows++;
  88. }
  89. cur=min(cur,test());
  90. i=j-1;
  91. }
  92. fout << cur << "\n";
  93. return 0;
  94. }
Compilation error #stdin compilation error #stdout 0s 0KB
stdin
Standard input is empty
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
Standard output is empty