結果

問題 No.2361 Many String Compare Queries
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:40:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,295 bytes
コンパイル時間 149 ms
コンパイル使用メモリ 81,924 KB
実行使用メモリ 107,628 KB
最終ジャッジ日時 2025-06-12 21:44:13
合計ジャッジ時間 4,762 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 WA * 4 TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    MOD = 10**18 + 3
    BASE = 911382629

    N, Q = map(int, sys.stdin.readline().split())
    S = sys.stdin.readline().strip()
    len_S = len(S)
    queries = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]

    # Precompute prefix hashes and powers for S
    prefix_hash_S = [0] * (len_S + 1)
    power_S = [1] * (len_S + 1)
    for i in range(len_S):
        prefix_hash_S[i+1] = (prefix_hash_S[i] * BASE + ord(S[i])) % MOD
        power_S[i+1] = (power_S[i] * BASE) % MOD

    def get_hash_S(l, r):
        # [l, r), 0-based
        if l >= r:
            return 0
        return (prefix_hash_S[r] - prefix_hash_S[l] * power_S[r - l]) % MOD

    for L, R in queries:
        T = S[L-1:R]
        len_T = R - L + 1

        # Precompute prefix hashes and powers for T
        prefix_hash_T = [0] * (len_T + 1)
        power_T = [1] * (len_T + 1)
        for i in range(len_T):
            prefix_hash_T[i+1] = (prefix_hash_T[i] * BASE + ord(T[i])) % MOD
            power_T[i+1] = (power_T[i] * BASE) % MOD

        def get_hash_T(l, r):
            if l >= r:
                return 0
            return (prefix_hash_T[r] - prefix_hash_T[l] * power_T[r - l]) % MOD

        total = 0

        for i in range(len_S):
            max_possible = min(len_T, len_S - i)
            low, high = 0, max_possible
            lcp = 0
            while low <= high:
                mid = (low + high) // 2
                if mid == 0:
                    current_hash_S = 0
                else:
                    current_hash_S = get_hash_S(i, i + mid)
                current_hash_T = get_hash_T(0, mid)
                if current_hash_S == current_hash_T:
                    lcp = mid
                    low = mid + 1
                else:
                    high = mid - 1
            if lcp < len_T:
                if i + lcp >= len_S:
                    continue
                if S[i + lcp] < T[lcp]:
                    count = len_S - (i + lcp)
                    total += count
            else:
                max_j = i + (len_T - 1)
                if max_j > len_S:
                    max_j = len_S
                count = max(0, max_j - i)
                total += count

        print(total)

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