J - Rash Cloyale

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const i64 INF = 0x3f3f3f3f3f3f3f3fLL;

template<class T>
class SegmentTree {
    struct Node {
        T val;
        Node(T x) : val(x) {}
        Node () : val(0) {}
    };
    int N;
    std::vector<T> a;
    std::vector<Node> tr;
    Node neutral;
    inline Node join(const Node &a, const Node &b) {
        return max(a.val, b.val);
    }
    void build(int node, int l, int r) {
        if (l == r) {
            tr[node] = Node(a[l]);
            return;
        }
        int mid = l+(r-l)/2, lc = (node << 1);
        build(lc, l, mid);
        build(lc+1, mid+1, r);
        tr[node] = join(tr[lc], tr[lc+1]);
    }
    Node query(int node, int l, int r, int ql, int qr) {
        if (r < l or qr < l or r < ql) return neutral;
        if (ql <= l and r <= qr) return tr[node];
        int mid = l+(r-l)/2, lc = (node << 1);
        return join(query(lc, l, mid, ql, std::min(qr, mid)),
                    query(lc+1, mid+1, r, std::max(mid+1, ql), qr));
    }
public:
    template<class MyIterator>
    SegmentTree (MyIterator begin, MyIterator end) {
        N = end-begin-1;
        tr.assign(4*N, 0);
        a = std::vector<T>(begin, end);
        build(1, 1, N);
    }
    SegmentTree (int n) : N(n) {
        tr.assign(4*N, 0);
        a.assign(N+1, 0);
    }
    T query(int l, int r) {
        return query(1, 1, N, l, r).val;
    }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int n; cin >> n;

  vector<i64> a(n + 1), b(n + 1), c;

  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; ++i) {
    cin >> b[i];
  }

  if (n == 1) {
    cout << a[0]+b[0] << '\n';
    return 0;
  }

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  c = b;
  reverse(c.begin() + 1, c.end());

  i64 answer = INF;

  vector<i64> d1(n + 1), d2(n + 1);

  for (int i = 1; i <= n; ++i) {
    d1[i] = a[i] + c[i];
  }

  d2[1] = a[1];
  for (int i = 2; i <= n; ++i) {
    d2[i] = a[i] + c[i - 1];
  }

  SegmentTree<int> S1(d1.begin(), d1.end());
  SegmentTree<int> S2(d2.begin(), d2.end());

  // for (int i = 1; i <= n; ++i) {
  //   cout << S1.query(i, i) << " \n"[i==n];
  // }

  // for (int i = 1; i <= n; ++i) {
  //   cout << S2.query(i, i) << " \n"[i==n];
  // }

  for (int i = 1; i <= n; i++) {
    int lo = 1, hi = n, ans = -1;

    while (lo <= hi) {
      int mid = (lo + hi)/2;

      i64 sum = a[i] + b[mid];

      mid = n - mid + 1;

      i64 mx = (
        i == mid
        ? max(S1.query(1, i-1), S1.query(i+1, n))
        : max({ S1.query(1, min(i, mid)-1), S1.query(max(i, mid)+1, n), S2.query(min(i, mid) + 1, max(i, mid)) })
      );

      // cout << mid << " -> " << mx << '\n';

      mid = n - mid + 1;

      if (sum >= mx) {
        ans = mid;
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }

    if (ans == -1) continue;

    // cout << i << " -> " << a[i] << " " << b[ans] << '\n';

    // mid
    answer = min(answer, a[i] + b[ans]);
  }

  cout << (answer == INF ? a.back()+b.back() : answer) << '\n';
}