結果
問題 |
No.2361 Many String Compare Queries
|
ユーザー |
![]() |
提出日時 | 2025-06-12 17:01:51 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,295 bytes |
コンパイル時間 | 241 ms |
コンパイル使用メモリ | 81,976 KB |
実行使用メモリ | 109,008 KB |
最終ジャッジ日時 | 2025-06-12 17:02:03 |
合計ジャッジ時間 | 4,983 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 2 WA * 4 TLE * 1 -- * 7 |
ソースコード
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()