結果

問題 No.2395 区間二次変換一点取得
コンテスト
ユーザー lam6er
提出日時 2025-03-20 20:49:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,481 bytes
コンパイル時間 174 ms
コンパイル使用メモリ 82,620 KB
実行使用メモリ 119,584 KB
最終ジャッジ日時 2025-03-20 20:49:28
合計ジャッジ時間 3,979 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 WA * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    B = int(data[idx])
    idx += 1
    Q = int(data[idx])
    idx += 1
    
    queries = []
    for _ in range(Q):
        L = int(data[idx])-1  # converting to 0-based
        idx += 1
        M = int(data[idx])-1
        idx += 1
        R = int(data[idx])-1
        idx += 1
        queries.append((L, M, R))
    
    # We'll track for each M in queries
    X = 1  # initial value is 1
    Y = 1
    Z = 1
    cnt_x = 0  # number of times step1 was applied to current M
    cnt_z = 0  # number of times step3 was applied to current M
    
    results = []
    for (L, M, R) in queries:
        # Check if current M is in [L, R] (all 0-based)
        in_L_R = L <= M <= R
        
        # Step 1: increment X if M is in [L, R]
        if in_L_R:
            cnt_x += 1
        
        # Step 2: update Y if M is in [L, R]
        if in_L_R:
            # Compute X_current and Z_prev
            X_current = 1 + cnt_x
            Z_prev = pow(3, cnt_z, B)
            Y = (3 * Y + 2 * X_current * Z_prev) % B
        
        # Step 3: multiply Z by 3 if M is in [L, R]
        if in_L_R:
            cnt_z += 1
        
        # Get current values mod B
        X_val = (1 + cnt_x) % B
        Z_val = pow(3, cnt_z, B)
        results.append(f"{X_val} {Y % B} {Z_val}")
    
    print('\n'.join(results))

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