結果
問題 |
No.2361 Many String Compare Queries
|
ユーザー |
![]() |
提出日時 | 2025-06-12 17:04:13 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,824 bytes |
コンパイル時間 | 408 ms |
コンパイル使用メモリ | 82,024 KB |
実行使用メモリ | 160,852 KB |
最終ジャッジ日時 | 2025-06-12 17:04:25 |
合計ジャッジ時間 | 4,880 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 4 WA * 2 TLE * 1 -- * 7 |
ソースコード
def main(): import sys input = sys.stdin.read data = input().split() idx = 0 N = int(data[idx]) idx += 1 Q = int(data[idx]) idx += 1 S = data[idx] idx += 1 # Precompute sum for each character sum_c = [0] * 26 for i in range(N): c = S[i] sum_c[ord(c) - ord('a')] += (N - i) # Precompute the list of indices for each character char_indices = [[] for _ in range(26)] for i in range(N): c = S[i] char_indices[ord(c) - ord('a')].append(i) for _ in range(Q): L = int(data[idx]) - 1 # Convert to 0-based idx += 1 R = int(data[idx]) - 1 idx += 1 T = S[L:R+1] t_len = len(T) if t_len == 0: print(0) continue c0 = T[0] c0_idx = ord(c0) - ord('a') # Compute A: sum of sum_c for c < c0 A = 0 for c_idx in range(c0_idx): A += sum_c[c_idx] # Compute B: sum over i where S[i] == c0 of count_i B = 0 for i in char_indices[c0_idx]: if i + t_len - 1 >= N: len_match = min(t_len, N - i) else: len_match = 0 while len_match < t_len and len_match < (N - i) and S[i + len_match] == T[len_match]: len_match += 1 count_i = min(len_match, t_len - 1) if len_match < t_len: if i + len_match < N and len_match < t_len: c_next = S[i + len_match] t_next = T[len_match] if c_next < t_next: count_i += (t_len - len_match - 1) B += count_i total = A + B print(total) if __name__ == '__main__': main()