test/library-checker/longest_increasing_subsequence.test.cpp

• View this file on GitHub
• Last update: 2026-10-26 21:56:22+09:00
• Problem: https://judge.yosupo.jp/problem/longest_increasing_subsequence

Depends on

• Longest Increasing Subsequence (algorithm/longest_increasing_subsequence.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/longest_increasing_subsequence"
#include <iostream>
#include <vector>

#include "algorithm/longest_increasing_subsequence.hpp"

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (auto& x : a) std::cin >> x;
    longest_increasing_subsequence lis(a);
    std::cout << lis.length() << '\n';
    for (int i : lis.indices()) std::cout << i << ' ';
    std::cout << '\n';
}

#line 1 "test/library-checker/longest_increasing_subsequence.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/longest_increasing_subsequence"
#include <iostream>
#include <vector>

#line 2 "algorithm/longest_increasing_subsequence.hpp"
#include <algorithm>
#include <cassert>
#include <functional>
#line 6 "algorithm/longest_increasing_subsequence.hpp"

template <class T, class Compare = std::less<T>>
struct longest_increasing_subsequence {
    explicit longest_increasing_subsequence(const std::vector<T>& a,
                                            Compare comp = {})
        : n(a.size()), pos(n) {
        std::vector<T> dp;
        for (int i = 0; i < n; i++) {
            auto it = std::lower_bound(dp.begin(), dp.end(), a[i], comp);
            pos[i] = it - dp.begin();
            if (it == dp.end()) {
                dp.push_back(a[i]);
            } else {
                *it = a[i];
            }
        }
        len = dp.size();
        cand.resize(len);
        for (int i = n - 1; i >= 0; i--) {
            int j = pos[i];
            if (j == len - 1 ||
                (!cand[j + 1].empty() && comp(a[i], a[cand[j + 1].back()]))) {
                cand[j].push_back(i);
            } else {
                pos[i] = -1;
            }
        }
        for (auto& c : cand) std::reverse(c.begin(), c.end());
    }
    int length() const { return len; }
    int position(int i) const {
        assert(0 <= i && i < n);
        return pos[i];
    }
    const std::vector<int>& candidates(int j) const {
        assert(0 <= j && j < len);
        return cand[j];
    }
    std::vector<int> indices() const {
        std::vector<int> res(len);
        for (int j = 0; j < len; j++) res[j] = cand[j].front();
        return res;
    }

  private:
    int n, len;
    std::vector<int> pos;
    std::vector<std::vector<int>> cand;
};
#line 6 "test/library-checker/longest_increasing_subsequence.test.cpp"

int main() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (auto& x : a) std::cin >> x;
    longest_increasing_subsequence lis(a);
    std::cout << lis.length() << '\n';
    for (int i : lis.indices()) std::cout << i << ' ';
    std::cout << '\n';
}

Back to top page