結果

問題 No.3052 Increasing Sliding Window Minimum
ユーザー warner1129
提出日時 2025-03-07 23:08:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 218 ms / 2,000 ms
コード長 2,739 bytes
コンパイル時間 3,959 ms
コンパイル使用メモリ 285,612 KB
実行使用メモリ 101,376 KB
最終ジャッジ日時 2025-03-07 23:08:52
合計ジャッジ時間 7,061 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

template<class F, class S>
ostream &operator<<(ostream &s, const pair<F, S> &v) {
    s << "(" << v.first << ", " << v.second << ")";
    return s;
}
template<ranges::range T> requires (!is_convertible_v<T, string_view>)
istream &operator>>(istream &s, T &&v) { 
    for (auto &&x : v) s >> x; 
    return s; 
}
template<ranges::range T> requires (!is_convertible_v<T, string_view>)
ostream &operator<<(ostream &s, T &&v) { 
    for (auto &&x : v) s << x << ' '; 
    return s; 
}

#ifdef LOCAL
template<class... T> void dbg(T... x) {
    char e{};
    ((cerr << e << x, e = ' '), ...);
}
#define debug(x...) dbg(#x, '=', x, '\n')
#else
#define debug(...) ((void)0)
#endif

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second

template<class T> inline constexpr T inf = numeric_limits<T>::max() / 2;
bool chmin(auto &a, auto b) { return (b < a and (a = b, true)); }
bool chmax(auto &a, auto b) { return (a < b and (a = b, true)); }

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;

constexpr i64 mod = 998244353;

void solve() {
    int n;
    cin >> n;

    vector<int> A(n);
    cin >> A;

    vector gre(n, vector<int>(n + 1));
    for (int i = 0; i < n; i++) {
        if (i) {
            gre[i] = gre[i - 1];
        }
        if (A[i] != -1) {
            for (int j = 1; j <= A[i]; j++) {
                gre[i][j]++;
            }
        }
    }

    vector<int> pos(n + 1, -1);
    for (int i = 0; i < n; i++) {
        if (A[i] != -1) {
            pos[A[i]] = i;
        }
    }

    vector<i64> dp(n + 1);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        int p = pos[i];
        vector<i64> ndp(n + 1);
        for (int j = 0; j <= n; j++) {
            if (dp[j] == 0) {
                continue;
            }
            if (p != -1) {
                if (p <= j + 1) {
                    (ndp[max(j, p + 1)] += dp[j]) %= mod;
                }
            } else {
                int c = j - (i - 1);
                if (j - 1 >= 0) {
                    c -= gre[j - 1][i];
                }
                (ndp[j] += dp[j] * c) %= mod;
                if (j < n and A[j] == -1) {
                    ndp[j + 1] += dp[j];
                }
                if (j + 1 < n and A[j + 1] == -1) {
                    (ndp[j + 2] += dp[j]) %= mod;
                }
            }
        }
        dp = ndp;
    }

    cout << dp[n] << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int t = 1;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}
0