test/atcoder/abc360_g.test.cpp

• View this file on GitHub
• Last update: 2025-08-08 18:52:16+09:00
• Problem: https://atcoder.jp/contests/abc360/tasks/abc360_g

Depends on

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

Code

// competitive-verifier: IGNORE
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc360/tasks/abc360_g
// 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 + 2);
 A[0]= -(1 << 30), A[N + 1]= 1 << 30;
 for (int i= 1; i <= N; ++i) cin >> A[i];
 auto [_, cand]= longest_increasing_subsequence(A);
 int K= cand.size();
 for (int i= 0; i + 1 < K; ++i) {
  int n= cand[i].size(), m= cand[i + 1].size();
  for (int j= 0, k= 0; j < n; ++j) {
   while (k < m && cand[i][j] + 2 > cand[i + 1][k]) ++k;
   if (k < m && A[cand[i][j]] + 2 <= A[cand[i + 1][k]]) return cout << K - 1 << '\n', 0;
  }
 }
 cout << K - 2 << '\n';
 return 0;
}

#line 1 "test/atcoder/abc360_g.test.cpp"
// competitive-verifier: IGNORE
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc360/tasks/abc360_g
// 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/abc360_g.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N;
 cin >> N;
 vector<int> A(N + 2);
 A[0]= -(1 << 30), A[N + 1]= 1 << 30;
 for (int i= 1; i <= N; ++i) cin >> A[i];
 auto [_, cand]= longest_increasing_subsequence(A);
 int K= cand.size();
 for (int i= 0; i + 1 < K; ++i) {
  int n= cand[i].size(), m= cand[i + 1].size();
  for (int j= 0, k= 0; j < n; ++j) {
   while (k < m && cand[i][j] + 2 > cand[i + 1][k]) ++k;
   if (k < m && A[cand[i][j]] + 2 <= A[cand[i + 1][k]]) return cout << K - 1 << '\n', 0;
  }
 }
 cout << K - 2 << '\n';
 return 0;
}

Back to top page