tests/02_sorting_searching_dp/longest_increasing_subsequence.test.cpp

View this file on GitHub
Last update: 2024-06-24 23:25:23+08:00
Problem: https://judge.yosupo.jp/problem/longest_increasing_subsequence

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/longest_increasing_subsequence"

#include "../../00_default/default.cpp"
#include "../../02_sorting_searching_dp/longest_increasing_subsequence.cpp"

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto &i : a)
    cin >> i;
  auto l = lis<int>(a);
  cout << sz(l) << '\n';
  for (int i : l)
    cout << i << ' ';
  cout << '\n';
}

#line 1 "tests/02_sorting_searching_dp/longest_increasing_subsequence.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/longest_increasing_subsequence"

#line 1 "00_default/default.cpp"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
constexpr int MAXN = 1e6 + 7;
constexpr int INF = 2e9;
constexpr ll INFF = 1e18;
constexpr ll MOD = 998244353;
#define mkp make_pair
#define F first
#define S second
#define pb emplace_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#line 1 "02_sorting_searching_dp/longest_increasing_subsequence.cpp"
// Modified from KACTL

template <class I> vector<I> lis(vector<I> &a) {
  if (a.empty())
    return {};
  vector<I> prev(sz(a));
  typedef pair<I, int> p;
  vector<p> res;
  for (int i = 0; i < sz(a); i++) {
    // 1. Change p{S[i], -1} -> p{S[i], INF} for longest non-decreasing
    // subsequence
    // 2. change p{S[i], -1} -> p{S[i], INF} and add greater<p>()
    // for longest decreasing subsequence
    // 3. Add greater<p>() for longest non-increasing subsequence
    auto it = lower_bound(all(res), p{a[i], -1});
    if (it == res.end())
      res.emplace_back(), it = res.end() - 1;
    *it = {a[i], i};
    prev[i] = it == res.begin() ? 0 : (it - 1)->second;
  }
  int L = sz(res), cur = res.back().second;
  vector<I> ans(L);
  while (L--)
    ans[L] = cur, cur = prev[cur];
  return ans;
}
#line 5 "tests/02_sorting_searching_dp/longest_increasing_subsequence.test.cpp"

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto &i : a)
    cin >> i;
  auto l = lis<int>(a);
  cout << sz(l) << '\n';
  for (int i : l)
    cout << i << ' ';
  cout << '\n';
}