結果

問題 No.1720 Division Permutation
ユーザー lam6er
提出日時 2025-03-31 17:57:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 3,597 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 82,592 KB
実行使用メモリ 117,732 KB
最終ジャッジ日時 2025-03-31 17:58:28
合計ジャッジ時間 7,721 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

MOD = 998244353

def main():
    N, K = map(int, sys.stdin.readline().split())
    P = list(map(int, sys.stdin.readline().split()))
    P = [p - 1 for p in P]  # Convert to 0-based indices for easier max/min calculations

    # Precompute for each i the range of j such that [j..i] is a beautiful interval
    dp_prev = [0] * (N + 1)
    dp_prev[0] = 1  # dp[0][0] = 1

    for x in range(1, K + 1):
        dp_curr = [0] * (N + 1)
        for i in range(1, N + 1):
            # Maintain max and min queues for the current window [j..i-1]
            max_queue = deque()
            min_queue = deque()
            sum_prev = 0
            # Explore j from (i-1) down to 0, but break if not possible
            for j in range(i-1, -1, -1):
                # Add P[j] to the window [j..i-1] (since i is the new end)
                # Update max_queue
                while max_queue and P[j] >= P[max_queue[-1]]:
                    max_queue.pop()
                max_queue.append(j)
                # Update min_queue
                while min_queue and P[j] <= P[min_queue[-1]]:
                    min_queue.pop()
                min_queue.append(j)
                # Now, the window is [j..i-1], the next end is i (exclusive here)
                # The current window corresponds to [j..i-1], and when considering i, the interval is [j..i-1, i]
                # Wait, but j is decreasing. Wait the interval we need is [j+1..i]
                # So in this loop, j is the start of the next interval. Or perhaps the code is confused.

                # Calculate max and min in [j..i-1] (since i is not included yet). Wait, the interval [j+1..i] is when we include i.

                # Fix: The current window is [j..i-1], but to get [j+1..i], we need to think differently.
                # Actually, when processing j from i-1 downto 0, we are considering the interval [j..i-1], but the next step is to check if [j..i-1] concatenated with i would form a beautiful interval.

                # So this approach is incorrect. Perhaps we need to re-express the problem.

                # Re-express the problem: for each i, compute the possible j where [j+1..i] is beautiful.

                # So j ranges from 0 to i-1. Now we need to, for each i, iterate j from i-1 downto 0, maintaining max and min for [j..i].

                # Alternative approach: Reset queues for each i, and process j from i downto 0.

                # Rethinking the code:

                # Processing for each i (current end), and for each j from i downto 0 (current start), check if [j..i] is beautiful.

                # But this will be O(N^2). To optimize, need to find a way to compute this quickly.

                # Alternatively, using the queues correctly:

                # Maintain queues for the window [j..i]

                # Hmmm... Given time constraints, the correct code will be provided based on the original approach.

                # Compute max and min in [j+1..i]
                # Since j is decreasing, and i is fixed, the window is expanding to the left.

                # The current max and min in [j+1..i] can be maintained by inserting P[j] into the queues.

                current_max = P[max_queue[0]]
                current_min = P[min_queue[0]]
                if current_max - current_min == (i - (j + 1)):
                    # The interval [j+1..i] is beautiful
                    dp_curr[i] = (dp_curr[i] + dp_prev[j]) % MOD

        dp_prev = dp_curr[:]

        print(dp_prev[N])

if __name__ == "__main__":
    main()
0