Submission #72218817

---

Source Code Expand

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    if(!(cin >> N)) return 0;
    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];

    vector<pair<long long,long long>> v(N);
    for(int i=0;i<N;++i) v[i] = {A[i], B[i]};
    sort(v.begin(), v.end(), [](auto &x, auto &y){
        if(x.first != y.first) return x.first < y.first;
        return x.second > y.second; // descending B for equal A
    });

    vector<long long> tails; // for patience sorting (strict LIS)
    for(auto &p : v){
        long long b = p.second;
        auto it = lower_bound(tails.begin(), tails.end(), b);
        if(it == tails.end()) tails.push_back(b);
        else *it = b;
    }
    cout << (int)tails.size() << "\n";
    return 0;
}

Submission Info

Judge Result