题解 | 小O的子序列最值

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

int main() {
    int n;
    cin >> n;
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    if (a.front() > b.back()) {  // 无法使 max(A) <= min(B)
        cout << -1 << '\n';
        return 0;
    }
    // 候选阈值：a 和 b 的所有值（去重）
    vector<long long> vals; vals.reserve(2*n);
    vals.insert(vals.end(), a.begin(), a.end());
    vals.insert(vals.end(), b.begin(), b.end());
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    long long ans = 0;
    for (long long t : vals) {
        long long cntA = upper_bound(a.begin(), a.end(), t) - a.begin();
        long long cntB = b.end() - lower_bound(b.begin(), b.end(), t);
        if (cntA > 0 && cntB > 0) ans = max(ans, cntA + cntB);
    }
    cout << ans << '\n';
    return 0;
}