Codeforces Round 990 (Div. 2) E题

#include <bits/stdc++.h>

using namespace std;
using Pii = pair<int, int>;

const int kMaxN = 2e5 + 5;

int T, n, ly[kMaxN];
Pii a[kMaxN];

struct Fenwick {
  int tr[kMaxN];
  void R() {
    fill(tr + 1, tr + n + 1, 0);
  }
  int Q(int x) { 
    return x ? Q(x - (x & -x)) + tr[x] : 0;
  }
  void A(int x, int s) { 
    x <= n && (A(x + (x & -x), s), tr[x] += s);
  }
} t1, t2;

Pii C() {
  int l = 0, r = n + 1;
  for (; l + 1 < r;) {
    int mid = (l + r) / 2;
    int ldown = t1.Q(mid - 1), lup = t1.Q(n) - ldown;
    int rdown = t2.Q(mid - 1), rup = t2.Q(n) - rdown;
    if (min(ldown, rdown) <= min(lup, rup)) {
      l = mid;
    } else {
      r = mid;
    }
  }
  int ldown = t1.Q(l - 1), lup = t1.Q(n) - ldown;
  int rdown = t2.Q(l - 1), rup = t2.Q(n) - rdown;
  return {min({lup, rup, ldown, rdown}), l};
}

int main() {
  cin.tie(0)->ios::sync_with_stdio(0);
  for (cin >> T; T--;) {
    cin >> n;
    t1.R(), t2.R();
    for (int i = 1; i <= n; i++) {
      cin >> a[i].first >> a[i].second;
      ly[i] = a[i].second;
    }
    sort(ly + 1, ly + n + 1);
    for (int i = 1; i <= n; i++) {
      a[i].second = lower_bound(ly + 1, ly + n + 1, a[i].second) - ly;
      t2.A(a[i].second, 1);
    }
    sort(a + 1, a + n + 1);
    int ans = 0, ansx, ansy;
    for (int i = 1, j = 1; i <= n; i++) { // 枚举x
      for (; j <= n && a[j].first < a[i].first; j++) {
        t2.A(a[j].second, -1);
        t1.A(a[j].second, 1);
      }
      Pii t = C();
      if (t.first > ans) {
        ans = t.first, ansx = a[i].first, ansy = ly[t.second];
        // cout << t.second << '\n';
      }
    }
    cout << ans << '\n' << ansx << ' ' << ansy << '\n';
  }
}