Codeforces Round #567 (Div. 2) E2. A Story of One Country (Hard)

https://codeforces.com/contest/1181/problem/E2

The solution is based on the following fact:

T(n) = T(x) + T(n - x) + min(x, n - x) = O(n log n)

Analysis: Looking at one specific element, when the element moves to the smaller group, it takes a time. These events happen log n times. Hence, the time complexity must be O(n log n).

// Time complexity: O(n log^2 n)
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--)

using namespace std;
using ll = long long;

template<class T> using minset = set<T, less<T>>;
template<class T> using maxset = set<T, greater<T>>;
int X1[100000], Y1[100000], X2[100000], Y2[100000];

struct mao {
  minset<pair<int, int>> rightward;
  maxset<pair<int, int>> leftward;
  minset<pair<int, int>> upward;
  maxset<pair<int, int>> downward;

  void insert(int id) {
    rightward.emplace(X1[id], id);
    leftward.emplace(X2[id], id);
    upward.emplace(Y1[id], id);
    downward.emplace(Y2[id], id);
  }

  void erase(int id) {
    rightward.erase({X1[id], id});
    leftward.erase({X2[id], id});
    upward.erase({Y1[id], id});
    downward.erase({Y2[id], id});
  }
};

template<class T>
vector<int> indices(T it, int k) {
  vector<int> res;
  for (int i = 0; i < k; i++) {
    res.push_back(it->second);
    it++;
  }
  return res;
}

bool f(mao &m) {
  const int n = m.rightward.size();
  if (n <= 1) return true;
  auto r = m.rightward.begin();
  auto l = m.leftward.begin();
  auto u = m.upward.begin();
  auto d = m.downward.begin();
  vector<int> v;
  int maxr = -1e9;
  int minl = 1e9;
  int maxu = -1e9;
  int mind = 1e9;
  for (int i = 0; i + 1 < n; i++, r++, l++, u++, d++) {
    maxr = max(maxr, X2[r->second]);
    minl = min(minl, X1[l->second]);
    maxu = max(maxu, Y2[u->second]);
    mind = min(mind, Y1[d->second]);
    auto rr = next(r);
    auto ll = next(l);
    auto uu = next(u);
    auto dd = next(d);
    if (maxr <= X1[rr->second]) {
      v = indices(m.rightward.begin(), i + 1);
      break;
    }
    if (minl >= X2[ll->second]) {
      v = indices(m.leftward.begin(), i + 1);
      break;
    }
    if (maxu <= Y1[uu->second]) {
      v = indices(m.upward.begin(), i + 1);
      break;
    }
    if (mind >= Y2[dd->second]) {
      v = indices(m.downward.begin(), i + 1);
      break;
    }
  }
  if (!v.empty()) {
    mao mm;
    for (int i : v) {
      m.erase(i);
      mm.insert(i);
    }
    return f(m) && f(mm);
  }
  return false;
}

int main() {
  int n;
  cin >> n;
  mao m;
  rep(i, n) {
    cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];
    m.insert(i);
  }
  cout << (f(m) ? "YES" : "NO") << '\n';
}

struct init {
  init() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
  }
} init;