結果

問題 No.515 典型LCP
ユーザー はむ吉🐹はむ吉🐹
提出日時 2017-05-07 15:15:44
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,270 bytes
コンパイル時間 168 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 280,188 KB
最終ジャッジ日時 2024-09-14 14:42:55
合計ジャッジ時間 4,775 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env pypy3

import functools
import os
import sys


CACHE_SIZE = 2 ** 16
INIT_VAL = 2 ** 31 - 1
REC_LIMIT = 100000


class SegmentTree4RMQ(object):

    def __init__(self, num_elems, init_val=sys.maxsize):
        self.num_elems = 1
        while self.num_elems < num_elems:
            self.num_elems *= 2
        self.data = [init_val for _ in range(self.num_elems * 2 - 1)]

    def update(self, k, a):
        k += self.num_elems - 1
        self.data[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[k * 2 + 1], self.data[k * 2 + 2])

    @functools.lru_cache(CACHE_SIZE)
    def rec(self, start, end, k, left, right):
        if right <= start or end <= left:
            return sys.maxsize
        elif start <= left and right <= end:
            return self.data[k]
        else:
            vl = self.rec(start, end, k * 2 + 1, left, (left + right) // 2)
            vr = self.rec(start, end, k * 2 + 2, (left + right) // 2, right)
            return min(vl, vr)

    def query(self, start, end):
        return self.rec(start, end, 0, 0, self.num_elems)


def generate_queries(n, x, d, m):
    for k in range(m):
        div, mod = divmod(x, n - 1)
        i = div + 1
        j = mod + 1
        if i > j:
            i, j = j, i
        else:
            j += 1
        yield i - 1, j - 1
        x = (x + d) % (n * (n - 1))


def sort_strings(ss):
    n = len(ss)
    res = sorted((ss[i], i) for i in range(n))
    ts, new2old = zip(*res)
    old2new = [None for _ in range(n)]
    for new, old in enumerate(new2old):
        old2new[old] = new
    return ts, tuple(old2new)


def solve(n, ss, m, x, d):
    ts, old2new = sort_strings(ss)
    st = SegmentTree4RMQ(n - 1)
    for i in range(n - 1):
        lcp = os.path.commonprefix(ts[i:i + 2])
        st.update(i, len(lcp))
    res = 0
    for i, j in generate_queries(n, x, d, m):
        a = old2new[i]
        b = old2new[j]
        if a > b:
            a, b = b, a
        res += st.query(a, b)
    return res


def main():
    sys.setrecursionlimit(REC_LIMIT)
    n = int(input())
    ss = [input() for _ in range(n)]
    m, x, d = (int(y) for y in input().split())
    print(solve(n, ss, m, x, d))


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