test/atcoder/abc134_e.test.cpp

• View this file on GitHub
• Last update: 2025-08-08 01:11:39+09:00
• Problem: https://atcoder.jp/contests/abc134/tasks/abc134_e

Depends on

• 最長増加部分列 (src/Misc/longest_increasing_subsequence.hpp)

Code

// competitive-verifier: IGNORE
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc134/tasks/abc134_e
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/Misc/longest_increasing_subsequence.hpp"
// 広義単調
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N;
 cin >> N;
 vector<int> A(N);
 for (int i= 0; i < N; ++i) cin >> A[N - i - 1];
 auto [_, cand]= longest_increasing_subsequence(A, false);
 cout << cand.size() << '\n';
 return 0;
}

#line 1 "test/atcoder/abc134_e.test.cpp"
// competitive-verifier: IGNORE
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc134/tasks/abc134_e
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 3 "src/Misc/longest_increasing_subsequence.hpp"
#include <algorithm>
template <class T> std::pair<std::vector<int>, std::vector<std::vector<int>>> longest_increasing_subsequence(const std::vector<T> &a, bool strict= true) {
 int n= a.size();
 std::vector<int> idx(n);
 std::vector<T> dp(n);
 int len= 0;
 if (strict)
  for (int i= 0; i < n; ++i) {
   auto it= std::lower_bound(dp.begin(), dp.begin() + len, a[i]);
   if (*it= a[i]; (idx[i]= it - dp.begin()) == len) ++len;
  }
 else
  for (int i= 0; i < n; ++i) {
   auto it= std::upper_bound(dp.begin(), dp.begin() + len, a[i]);
   if (*it= a[i]; (idx[i]= it - dp.begin()) == len) ++len;
  }
 std::vector<std::vector<int>> cand(len);
 for (int i= n; i--;) {
  if (idx[i] == len - 1 || (!cand[idx[i] + 1].empty() && a[i] < a[cand[idx[i] + 1].back()])) cand[idx[i]].emplace_back(i);
  else idx[i]= -1;
 }
 for (auto &c: cand) std::reverse(c.begin(), c.end());
 return {idx, cand};
}
#line 8 "test/atcoder/abc134_e.test.cpp"
// 広義単調
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N;
 cin >> N;
 vector<int> A(N);
 for (int i= 0; i < N; ++i) cin >> A[N - i - 1];
 auto [_, cand]= longest_increasing_subsequence(A, false);
 cout << cand.size() << '\n';
 return 0;
}

Back to top page