結果

問題 No.3052 Increasing Sliding Window Minimum
ユーザー suisen
提出日時 2024-02-10 00:22:16
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 332 ms / 2,000 ms
コード長 1,451 bytes
コンパイル時間 2,469 ms
コンパイル使用メモリ 102,652 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-01-25 15:02:36
合計ジャッジ時間 7,238 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 >= 0; ++d) {
                if (p[r] != -1 and p[r] != v) continue;
                if (p[r] == -1 and q[v] != -1) continue;
                dp[r] += pd[r - d];
            }
            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