結果

問題 No.3052 Increasing Sliding Window Minimum
ユーザー suisen
提出日時 2024-02-10 00:27:03
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 251 ms / 2,000 ms
コード長 1,655 bytes
コンパイル時間 5,573 ms
コンパイル使用メモリ 103,280 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-01-25 15:02:48
合計ジャッジ時間 6,426 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;
    std::vector<Int> spd(n + 2);

    for (int v = 1; v <= n; ++v) {
        if (int i = q[v]; i != -1) {
            for (int j = i; j <= n; ++j) --cnt[j];
        }
        for (int r = 0; r <= n; ++r) {
            spd[r + 1] = spd[r] + pd[r];
        }

        std::vector<Int> dp(n + 1);
        for (int r = 0; r <= n; ++r) {
            bool ok = true;
            if (p[r] != -1 and p[r] != v) ok = false;
            if (p[r] == -1 and q[v] != -1) ok = false;
            if (ok) {
                dp[r] += spd[r];
                if (r - K >= 0) {
                    dp[r] -= spd[r - K];
                }
            }

            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