結果

問題 No.2361 Many String Compare Queries
コンテスト
ユーザー lam6er
提出日時 2025-04-09 21:02:55
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,992 bytes
コンパイル時間 639 ms
コンパイル使用メモリ 82,336 KB
実行使用メモリ 70,524 KB
最終ジャッジ日時 2025-04-09 21:05:12
合計ジャッジ時間 5,340 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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])
    Q = int(data[idx + 1])
    idx += 2
    S = data[idx]
    idx += 1
    queries = []
    for _ in range(Q):
        L = int(data[idx]) - 1  # convert to 0-based
        R = int(data[idx + 1]) - 1
        queries.append((L, R))
        idx += 2

    for L, R in queries:
        len_T = R - L + 1
        T = S[L:L + len_T]
        P = T + '#' + S
        n = len(P)
        Z = [0] * n
        l, r = 0, 0
        Z[0] = len_T  # the first part is T itself, so Z[0] is not used
        for i in range(1, n):
            if i > r:
                l = r = i
                while r < n and P[r - l] == P[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 P[r - l] == P[r]:
                        r += 1
                    Z[i] = r - l
                    r -= 1

        offset = len_T + 1
        total = 0
        for i in range(N):
            pos_in_P = offset + i
            l_i = Z[pos_in_P]
            l_i = min(l_i, len_T)
            if l_i >= len_T:
                max_valid = len_T - 1
                possible = N - i
                add = min(max_valid, possible)
                total += add
            else:
                if l_i < len_T:
                    if i + l_i >= N:
                        part1 = 0
                    else:
                        char_s = S[i + l_i]
                        char_t = T[l_i] if l_i < len_T else ''
                        if char_s < char_t:
                            part1 = (N - (i + l_i))
                            total += part1
                    part2 = min(l_i, len_T - 1)
                    total += part2
        print(total)

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