結果

問題 No.2361 Many String Compare Queries
コンテスト
ユーザー qwewe
提出日時 2025-05-14 12:51:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,629 bytes
コンパイル時間 517 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 271,016 KB
最終ジャッジ日時 2025-05-14 12:53:20
合計ジャッジ時間 5,316 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 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
    queries = []
    for _ in range(Q):
        L = int(data[idx]) - 1  # 0-based
        idx += 1
        R = int(data[idx]) - 1  # 0-based
        idx += 1
        queries.append((L, R))
    
    for L, R in queries:
        M = R - L + 1
        T = S[L:L+M]
        concat = T + '#' + S
        n = len(concat)
        Z = [0] * n
        Z[0] = 0
        l, r = 0, 0
        for i in range(1, n):
            if i > r:
                l = r = i
                while r < n and concat[r - l] == concat[r]:
                    r += 1
                Z[i] = r - l
                r -= 1
            else:
                k = i - l
                if Z[k] < r - i + 1:
                    Z[i] = Z[k]
                else:
                    l = i
                    while r < n and concat[r - l] == concat[r]:
                        r += 1
                    Z[i] = r - l
                    r -= 1
        
        case_B = 0
        case_A = 0
        offset = M + 1
        for i in range(N):
            l_i = Z[offset + i]
            case_B += min(l_i, M - 1)
            if l_i < M:
                if i + l_i >= N:
                    continue
                if L + l_i > R:
                    continue
                if S[i + l_i] < S[L + l_i]:
                    contribution = N - (i + l_i)
                    case_A += contribution
        
        print(case_B + case_A)

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