test/library_checker/other/longest_increasing_subsequence.test.cpp

• View this file on GitHub
• Last update: 2024-11-04 03:12:13+09:00
• Problem: https://judge.yosupo.jp/problem/longest_increasing_subsequence

Depends on

• Longest Increasing Subsequence (lib/dp/LIS.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/longest_increasing_subsequence"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/dp/LIS.hpp"

int main(){
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    vector<int> LIS = construct_LIS(a);
    cout << (int) LIS.size() << "\n";
    for(auto x : LIS){
        cout << x << " ";
    }
    cout << "\n";
}

#line 1 "test/library_checker/other/longest_increasing_subsequence.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/longest_increasing_subsequence"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/dp/LIS.hpp"

/**
 * @brief Longest Increasing Subsequence
 * @docs docs/dp/LIS.md
 */

template <typename T>
int LIS(vector<T> a, bool is_strong = true){
    const long long INF = 0x1fffffffffffffff;
    int n = (int) a.size();
    vector<long long> dp(n, INF);
    for(int i = 0; i < n; ++i){
        if(is_strong) *lower_bound(dp.begin(), dp.end(), a[i]) = a[i];
        else *upper_bound(dp.begin(), dp.end(), a[i]) = a[i];
    }
    return lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}

template <typename T>
vector<int> construct_LIS(vector<T> a, bool is_strong = true){
    const long long INF = 0x1fffffffffffffff;
    int n = (int) a.size();
    vector<long long> dp(n, INF);
    vector<vector<int>> idx(n);
    for(int i = 0; i < n; ++i){
        if(is_strong){
            auto iter = lower_bound(dp.begin(), dp.end(), a[i]);
            *iter = a[i];
            idx[(int) (iter - dp.begin())].emplace_back(i);
        } else{
            auto iter = upper_bound(dp.begin(), dp.end(), a[i]);
            *iter = a[i];
            idx[(int) (iter - dp.begin())].emplace_back(i);
        }
    }
    int k = lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
    vector<int> res;
    int now = n;
    for(int i = k - 1; i >= 0; --i){
        auto iter = upper_bound(idx[i].begin(), idx[i].end(), now);
        iter--;
        now = *iter;
        res.push_back(now);
    }
    reverse(res.begin(), res.end());
    return res;
}
#line 6 "test/library_checker/other/longest_increasing_subsequence.test.cpp"

int main(){
    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    vector<int> LIS = construct_LIS(a);
    cout << (int) LIS.size() << "\n";
    for(auto x : LIS){
        cout << x << " ";
    }
    cout << "\n";
}

Back to top page