結果

問題 No.2361 Many String Compare Queries
コンテスト
ユーザー gew1fw
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0