fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const int N = 1e5 + 5;
  4. const int MAX = 1e6 + 6;
  5. vector < int > v[MAX];
  6. int x , y;
  7. int n;
  8. int ans;
  9. int bit[2][MAX];
  10. vector < int > ys;
  11. set < int > s;
  12. void update(int k , int idx , int val){
  13.     while(idx < MAX){
  14.         bit[k][idx] += val;
  15.         idx += idx & -idx;
  16.     }
  17. }
  18. int query(int k , int idx){
  19.     int res = 0;
  20.     while(idx){
  21.         res += bit[k][idx];
  22.         idx -= idx & -idx;
  23.     }
  24.     return res;
  25. }
  26. inline int get(int a , int b , int c , int d){
  27.     return max(max(a , b) , max(c , d));
  28. }
  29. inline int cost(int y){
  30.     int lftu = query(0 , y);
  31.     int lftd = query(0 , MAX - 1) - lftu;
  32.     int rgtu = query(1 , y);
  33.     int rgtd = query(1 , MAX - 1) - rgtu;
  34.     return get(lftu , lftd , rgtu , rgtd);
  35. }
  36. int main(){
  37.     freopen("balancing.in" , "r" , stdin);
  38.     freopen("balancing.out" , "w" , stdout);
  39.     scanf("%d" , &n);
  40.     memset(bit , 0 , sizeof(bit));
  41.     for(int i = 1 ; i <= n ; ++i){
  42.         scanf("%d %d" , &x , &y);
  43.         assert(y > 0);
  44.         assert(x > 0);
  45.         s.insert(y);
  46.         update(1 , y , 1);
  47.         v[x].emplace_back(y);
  48.     }
  49.     ys.clear();
  50.     for(int x : s){
  51.         ys.emplace_back(x);
  52.     }
  53.     ans = n;
  54.     for(int x = 1 ; x < MAX ; ++x){
  55.         if(v[x].empty()){
  56.             continue;
  57.         }
  58.         sort(v[x].begin() , v[x].end());
  59.         for(int y : v[x]){
  60.             update(0 , y , 1);
  61.             update(1 , y , -1);
  62.         }
  63.         int l = 0;
  64.         int r = int(ys.size()) - 1;
  65.         while(l + 3 < r){
  66.             int mid1 = l + l + r;
  67.             int mid2 = l + r + r;
  68.             mid1 /= 3;
  69.             mid2 /= 3;
  70.             int x = cost(ys[mid1]);
  71.             int y = cost(ys[mid2]);
  72.             ans = min(ans , min(x , y));
  73.             if(x <= y){
  74.                 r = mid2;
  75.             }
  76.             else{
  77.                 l = mid1;
  78.             }
  79.         }
  80.         for(int i = l ; i <= r ; ++i){
  81.             ans = min(ans , cost(ys[i]));
  82.         }
  83.     }
  84.     printf("%d\n" , ans);
  85. }
Success #stdin #stdout 0.02s 22984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ALKija
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!