#1176652 (C++23(gnu拡張gcc16)) No.3618 Omega Cat（Making ver.）

• 問題: No.3618 Omega Cat（Making ver.）
• ユーザー: KEYBO
• 提出日時: 2026-08-14 19:09:19
• 言語: C++23(gnu拡張gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 1,039 ms / 2,000 ms
• コード長: 3,657 bytes
• コンパイル時間: 7,043 ms
• コンパイル使用メモリ: 404,844 KB
• 実行使用メモリ: 84,716 KB
• 最終ジャッジ日時: 2026-08-14 19:09:43
• 合計ジャッジ時間: 18,543 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_0

サブタスク	配点	結果
サンプル	0 %	AC * 1
小課題1	20 %	AC * 5
小課題2	20 %	AC * 12
小課題3	40 %	AC * 24
小課題4	20 %	AC * 38
合計	3.5 * 100% = 350 点

ソースコード

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;

using ll = int64_t;
using ul = uint64_t;
using ld = long double;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vs = vector<string>;
using vb = vector<bool>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvd = vector<vd>;
using vvc = vector<vc>;
using vvb = vector<vb>;
using vvl = vector<vl>;
using mint = modint998244353;
using vm = vector<mint>;

template <typename X>
struct SegTree {
  using FX = function<X(X, X)>; // X○X -> Xとなる関数の型
  int N; // 葉の数
  FX fx; // 関数
  const X ex; // 単位元
  vector<X> data; // セグ木

  SegTree(int N_, FX fx_, X ex_) : N(1), fx(fx_), ex(ex_), data(N_*4, ex_) {
    while(N_ > N) N *= 2;
  }
  // 0 <= pos <= N - 1
  void set(int pos, X x) {
    data[pos + N - 1] = x;
  }
  void build() {
    for (int pos = N - 2; pos >= 0; pos--) {
      data[pos] = fx(data[pos*2 + 1], data[pos*2 + 2]);
    }
  }
  X get(int pos) {
    return data[pos + N - 1];
  }

  // 1点更新
  // 0 <= pos <= N - 1
  void update(int pos, X x) {
    pos += N - 1;
    data[pos] = x;
    while(pos > 0) {
      pos = (pos - 1)/2; // 親へ伝播
      data[pos] = fx(data[pos*2 + 1], data[pos*2 + 2]);
    }
  }

  // クエリ呼び出し
  // 0 <= a <= N - 1
  // 1 <= b <= N
  X query(int a, int b) { return query_sub(a, b, 0, 0, N); }

  // クエリ回答
  X query_sub(int a, int b, int pos, int l, int r) {
    // 範囲外
    if (r <= a || b <= l) return ex;
    // 完全に含まれる
    else if (a <= l && r <= b) return data[pos];
    // 一部だけ含まれる
    else {
      X L = query_sub(a, b, pos*2 + 1, l, (l + r)/2);
      X R = query_sub(a, b, pos*2 + 2, (l + r)/2, r);
      return fx(L, R);
    }
  }
};

void solve() {
  int N;
  cin >> N;
  vl H(N);
  for (int i = 0; i < N; i++) {
    cin >> H[i];
  }

  vl L = H,R = H;
  for (int i = 0; i < N; i++) L[i] -= i;
  for (int i = 0; i < N; i++) R[N - 1 - i] -= i;
  set<ll> Lnum,Rnum;
  for (auto x : L) Lnum.insert(x);
  Lnum.insert(-1e15);
  for (auto x : R) Rnum.insert(x);
  Rnum.insert(1e15);
  map<ll,int> Ltra,Rtra;
  int cnt = 0;
  for (auto x : Lnum) {
    Ltra[x] = cnt;
    cnt++;
  }
  cnt = 0;
  for (auto x : Rnum) {
    Rtra[x] = cnt;
    cnt++;
  }
  vi Ldec(N),Rdec(N);
  for (int i = 0; i < N; i++) Ldec[i] = Ltra[L[i]];
  for (int i = 0; i < N; i++) Rdec[i] = Rtra[R[i]];
  int Min = Ltra[-1e15],Max = Rtra[1e15];

  auto fx = [](ll x1, ll x2) -> int { return min(x1, x2); };
  ll ex = 1e9;
  vector<SegTree<ll>> dp(4, SegTree<ll>(N + 1, fx, ex));
  dp[0].update(Rdec[0], -1);
  dp[0].update(Max, 0);

  for (int i = 1; i < N; i++) {
    for (int j = 3; j >= 0; j--) {
      // 折れる
      if (j == 3) int none = 1;
      else if (i == N - 1 && j == 2) continue;
      else if (j%2 == 0) {
        dp[j + 1].update(Ldec[i], min(dp[j + 1].get(Ldec[i]), dp[j].query(Rdec[i], N + 1) - 1));
        dp[j + 1].update(Min, min(dp[j + 1].get(Min), dp[j].query(0, N + 1)));
      }
      else {
        dp[j + 1].update(Rdec[i], min(dp[j + 1].get(Rdec[i]), dp[j].query(0, Ldec[i] + 1) - 1));
        dp[j + 1].update(Max, min(dp[j + 1].get(Max), dp[j].query(0, N + 1)));
      }

      // 単調
      if (j%2 == 0) {
        ll bef = dp[j].query(Rdec[i], N + 1);
        dp[j].update(Rdec[i], bef - 1);
      }
      else {
        ll bef = dp[j].query(0, Ldec[i] + 1);
        dp[j].update(Ldec[i], bef - 1);
      }
    }
  }
  cout << N + dp[3].query(0, N + 1) << endl;
  return;
}

int main() {
  int T;
  cin >> T;
  while(T > 0) {
    solve();
    T--;
  }
  return 0;
}