結果

問題 No.3052 Increasing Sliding Window Minimum
ユーザー 王開育
提出日時 2025-03-08 00:21:21
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 355 ms / 2,000 ms
コード長 3,173 bytes
コンパイル時間 3,668 ms
コンパイル使用メモリ 281,488 KB
実行使用メモリ 198,912 KB
最終ジャッジ日時 2025-03-08 00:21:30
合計ジャッジ時間 8,776 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) begin(x), end(x)
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#ifdef LOCAL
#define HEHE freopen("in.txt", "r", stdin);
#define debug(HEHE...) cerr << #HEHE << " = ", dout(HEHE)
void dout() { std::cerr << '\n'; }
template <typename T, typename ...U>
void dout(T t, U ...u) { std::cerr << t << ' '; dout(u...); }
#else
#define HEHE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 7122
#endif
using namespace std;

#define chmax(a, b) (a) = (a) > (b) ? (a) : (b)
#define chmin(a, b) (a) = (a) < (b) ? (a) : (b)

#define int long long

const int mod = 998244353;
void add(int &x, int v) {
    x += v;
    if (x >= mod) x -= mod;
}
struct BIT {
    vector<int> bit;
    int n;
    void init(int _n) {
        n = _n;
        bit.assign(n + 5, 0);
    }
    void upd(int x, int v) {
        for (int i = x; i <= n; i += i & -i)
            bit[i] += v;
    }
    int qry(int x) {
        int res = 0;
        for (int i = x; i > 0; i -= i & -i) res += bit[i];
        return res;
    }
} bit;
void solve() {
    int n;
    cin >> n;
    bit.init(n);
    vector<int> a(n + 1), pos(n + 1, -1);
    FOR (i, 1, n) {
        cin >> a[i];
        if (a[i] != -1) {
            pos[a[i]] = i;
            bit.upd(i, 1);
        }
    }
    // a[i] >= min(a[i-1], a[i-2])
    // a[1] = 1 or a[2] = 1
    // 1, 12345, 12345, 
    // 1 2 3 4... n/2
    // dp[i][j] : #(1~i 裡最後一個放在 j)
    // 123...
    // dp[i][j] = dp[i-1][j] * (1 到 j 裡有幾個空格)
    // (1 到 j 裡有幾個空格) = j - (i-1) - (1~j裡有幾個數字 > i)
    vector<vector<int>> dp(n + 1, vector<int> (n + 1, 0));
    {   
        if (pos[1] == -1) {
            if (a[1] == -1) dp[1][1] = 1;
            if (a[2] == -1) dp[1][2] = 1;
        }
        else {
            if (pos[1] == 1) dp[1][1] = 1;
            if (pos[1] == 2) dp[1][2] = 1;
            bit.upd(pos[1], -1);
        }
    }
    for (int i = 2; i <= n; i++) {
        if (pos[i] != -1) {
            bit.upd(pos[i], -1);
        }
        if (pos[i] != -1) {
            // debug(pos[i]);
            for (int j = pos[i]+1; j <= n; j++) {
                dp[i][j] = dp[i-1][j];
            }
            FOR (j, max(1ll, pos[i] - 2), pos[i] - 1) add(dp[i][pos[i]], dp[i-1][j]);
        } else {
            // debug(i, pos[i]);
            FOR (j, i, n) {
                if (a[j] == -1) {
                    if (j >= 2) add(dp[i][j], dp[i-1][j-1]);
                    if (j >= 3) add(dp[i][j], dp[i-1][j-2]);
                }
                if ((j-i+1-bit.qry(j)) >= 0) {
                    // debug(i,j, (j-i+1-bit.qry(j)));
                    add(dp[i][j], dp[i-1][j] * (j-i+1-bit.qry(j)) % mod);
                }
                // assert((j-i+1-bit.qry(j))>=0);   
            }
        }
        // debug(i);
        // FOR (j, 1, n) {
        //     cout << dp[i][j] << " \n"[j == n];
        // }
        // cout << "===================\n";
    }
    cout << dp[n][n] << '\n';
}

signed main() {
    HEHE
    // freopen("Out.txt", "w", stdout);
    int t; cin >> t;
    while (t--) solve();
}
0