結果

問題 No.2361 Many String Compare Queries
コンテスト
ユーザー qwewe
提出日時 2025-05-14 12:51:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,680 bytes
コンパイル時間 436 ms
コンパイル使用メモリ 82,720 KB
実行使用メモリ 271,592 KB
最終ジャッジ日時 2025-05-14 12:53:24
合計ジャッジ時間 5,023 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 6 TLE * 1 -- * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

def compute_z(s):
    n = len(s)
    Z = [0] * n
    Z[0] = n
    l, r = 0, 0
    for i in range(1, n):
        if i > r:
            l = r = i
            while r < n and s[r - l] == s[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 s[r - l] == s[r]:
                    r += 1
                Z[i] = r - l
                r -= 1
    return Z

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1
    S = input[ptr]
    ptr += 1
    queries = []
    for _ in range(Q):
        L = int(input[ptr]) - 1  # converting to 0-based
        ptr += 1
        R = int(input[ptr]) - 1
        ptr += 1
        queries.append((L, R))
    
    for L, R in queries:
        M = R - L + 1
        T = S[L:L+M]
        T_prime = T + '#' + S
        Z = compute_z(T_prime)
        ans = 0
        for i in range(N):
            pos = M + 1 + i
            if pos >= len(Z):
                l_i = 0
            else:
                l_i = min(Z[pos], M)
            count_B = min(l_i, M-1)
            count_A = 0
            if l_i < M:
                if i + l_i >= N:
                    pass
                else:
                    if L + l_i > R:
                        pass
                    else:
                        if S[i + l_i] < S[L + l_i]:
                            count_A = N - (i + l_i)
            ans += count_B + count_A
        print(ans)

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