結果

問題 No.469 区間加算と一致検索の問題
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:40:50
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 346 ms / 5,000 ms
コード長 1,294 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 130,312 KB
最終ジャッジ日時 2025-03-31 17:42:20
合計ジャッジ時間 11,317 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 49
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1

    mod1 = 10**18 + 3
    a1 = 911382629
    mod2 = 10**18 + 7
    a2 = 3571428571

    pow_a1 = [1] * (N + 2)
    for i in range(1, N + 2):
        pow_a1[i] = (pow_a1[i-1] * a1) % mod1

    pow_a2 = [1] * (N + 2)
    for i in range(1, N + 2):
        pow_a2[i] = (pow_a2[i-1] * a2) % mod2

    hash_map = {}
    h1 = 0
    h2 = 0
    hash_map[(h1, h2)] = 0

    for i in range(1, Q + 1):
        query = input[ptr]
        ptr += 1
        if query == '!':
            L = int(input[ptr])
            ptr += 1
            R = int(input[ptr])
            ptr += 1
            K = int(input[ptr])
            ptr += 1
            delta1 = K * (pow_a1[L] - pow_a1[R]) % mod1
            delta2 = K * (pow_a2[L] - pow_a2[R]) % mod2
            h1 = (h1 + delta1) % mod1
            h2 = (h2 + delta2) % mod2
            current_pair = (h1, h2)
            if current_pair not in hash_map:
                hash_map[current_pair] = i
        else:
            prev_h1 = h1
            prev_h2 = h2
            current_pair = (prev_h1, prev_h2)
            print(hash_map.get(current_pair, 0))
    
if __name__ == '__main__':
    main()
0