結果

問題 No.3052 Increasing Sliding Window Minimum
ユーザー suisen
提出日時 2024-02-10 00:02:11
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 255 ms / 2,000 ms
コード長 1,463 bytes
コンパイル時間 2,380 ms
コンパイル使用メモリ 102,260 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2025-01-25 15:02:25
合計ジャッジ時間 6,465 ms
ジャッジサーバーID
（参考情報） 		judge7 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

#include <atcoder/modint>

using Int = atcoder::modint998244353;

constexpr int K = 2;

Int solve(int n, const std::vector<int>& p) {
    std::vector<int> q(n + 1, -1);
    for (int i = 1; i <= n; ++i) if (p[i] != -1) {
        q[p[i]] = i;
    }
    std::vector<int> cnt(n + 1);
    for (int i = 1; i <= n; ++i) {
        cnt[i] = cnt[i - 1] + (p[i] != -1);
    }

    std::vector<Int> pd(n + 1);
    pd[0] = 1;
    for (int v = 1; v <= n; ++v) {
        if (int i = q[v]; i != -1) {
            for (int j = i; j <= n; ++j) --cnt[j];
        }
        std::vector<Int> dp(n + 1);
        for (int r = 0; r <= n; ++r) {
            for (int d = 1; d <= K and r + d <= n; ++d) {
                if (p[r + d] != -1 and p[r + d] != v) continue;
                if (p[r + d] == -1 and q[v] != -1) continue;
                dp[r + d] += pd[r];
            }
            if (q[v] == -1) {
                dp[r] += (r - (v - 1) - cnt[r]) * pd[r];
            } else if (q[v] <= r) {
                dp[r] += pd[r];
            }
        }
        pd.swap(dp);
    }
    return pd[n];
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        int n;
        std::cin >> n;
        std::vector<int> a(n + 1, -1);
        for (int i = 1; i <= n; ++i) {
            std::cin >> a[i];
        }
        std::cout << solve(n, a).val() << std::endl;
    }
}
0