結果
| 問題 | No.515 典型LCP |
| ユーザー |
👑  rin204
|
| 提出日時 | 2022-10-02 18:01:11 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,887 bytes |
| コンパイル時間 | 247 ms |
| コンパイル使用メモリ | 87,180 KB |
| 実行使用メモリ | 222,668 KB |
| 最終ジャッジ日時 | 2023-08-26 15:52:31 |
| 合計ジャッジ時間 | 5,501 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| 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 | -- | - |
ソースコード
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
class SegTree:
def __init__(self, n, e, ope, lst=[]):
self.N0 = 2 ** (n - 1).bit_length()
self.e = e
self.ope = ope
self.data = [e] * (2 * self.N0)
if lst:
for i in range(n):
self.data[self.N0 + i] = lst[i]
for i in range(self.N0 - 1, 0, -1):
self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])
def build(self):
for i in range(self.N0 - 1, 0, -1):
self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])
def update(self, i, x): #a_iの値をxに更新
i += self.N0
self.data[i] = x
while i > 1:
i >>= 1
self.data[i] = self.ope(self.data[2 * i], self.data[2 * i + 1])
def add(self, i, x):
self.update(i, x + self.get(i))
def set(self, i, x):
self.data[self.N0 + i] = x
def query(self, l, r): #区間[l, r)での演算結果
if r <= l:
return self.e
lres = self.e
rres = self.e
l += self.N0
r += self.N0
while l < r:
if l & 1:
lres = self.ope(lres, self.data[l])
l += 1
if r & 1:
r -= 1
rres = self.ope(self.data[r], rres)
l >>= 1
r >>= 1
return self.ope(lres, rres)
def get(self, i): #a_iの値を返す
return self.data[self.N0 + i]
def SA_IS(a):
a += [0]
k = max(a) + 1
n = len(a)
def induce_l(sa, a, n, k, stype):
bucket = get_buckets(a, k, 1)
for i in range(n):
j = sa[i] - 1
if j >= 0 and (not stype[j]):
sa[bucket[a[j]]] = j
bucket[a[j]] += 1
def induce_s(sa, a, n, k, stype):
bucket = get_buckets(a, k, 0)
for i in range(n)[::-1]:
j = sa[i] - 1
if j >= 0 and stype[j]:
bucket[a[j]] -= 1
sa[bucket[a[j]]] = j
def get_buckets(a, k, start = 0):
bucket = [0] * k
for item in a:
bucket[item] += 1
s = 0
for i in range(k):
s += bucket[i]
bucket[i] = s - (bucket[i] if start else 0)
return bucket
def set_lms(a, n, k, default_order):
bucket = get_buckets(a, k)
sa = [-1] * n
for i in default_order[::-1]:
bucket[a[i]] -= 1
sa[bucket[a[i]]] = i
return sa
def induce(a, n, k, stype, default_order):
sa = set_lms(a, n, k, default_order)
induce_l(sa, a, n, k, stype)
induce_s(sa, a, n, k, stype)
return sa
def rename_LMS_substring(sa, a, n, stype, LMS, l):
sa = [_s for _s in sa if LMS[_s]]
tmp = [-1] * (n//2) + [0]
dupl = 0
for _ in range(1, l):
i, j = sa[_-1], sa[_]
for ii in range(n):
if a[i+ii] != a[j+ii] or stype[i+ii] != stype[j+ii]:
break
if ii and (LMS[i+ii] or LMS[j+ii]):
dupl += 1
break
tmp[j//2] = _ - dupl
tmp = [t for t in tmp if t >= 0]
return tmp, dupl
def calc(a, n, k):
stype = [1] * n
for i in range(n-1)[::-1]:
if a[i] > a[i+1] or (a[i] == a[i+1] and stype[i+1] == 0):
stype[i] = 0
LMS = [1 if stype[i] and not stype[i-1] else 0 for i in range(n-1)] + [1]
l = sum(LMS)
lms = [i for i in range(n) if LMS[i]]
sa = induce(a, n, k, stype, lms)
renamed_LMS, dupl = rename_LMS_substring(sa, a, n, stype, LMS, l)
if dupl:
sub_sa = calc(renamed_LMS, l, l - dupl)
else:
sub_sa = [0] * l
for i in range(l):
sub_sa[renamed_LMS[i]] = i
lms = [lms[sub_sa[i]] for i in range(l)]
sa = induce(a, n, k, stype, lms)
return sa
sa = calc(a, n, k)
return sa
def LCP(s, n, sa):
lcp = [-1]*(n+1)
rank = [0]*(n+1)
for i in range(n+1): rank[sa[i]] = i
h = 0
lcp[0] = 0
for i in range(n):
j = sa[rank[i] - 1]
if h > 0: h -= 1
while j+h < n and i+h < n and s[j+h]==s[i+h]:
h += 1
lcp[rank[i] - 1] = h
return lcp
n = int(input())
S = []
le = []
ind = 0
for _ in range(n):
le.append(ind)
for s in input():
S.append(ord(s))
ind += 1
sa = SA_IS(S)
lcp = LCP(S, ind, sa)
seg = SegTree(ind, 1 << 30, min, lcp[1:])
inv = [0] * ind
for i, s in enumerate(sa[1:]):
inv[s] = i
pos = [0] * n
for i, l in enumerate(le):
pos[i] = inv[l]
def make_query(m, x, d):
for _ in range(m):
i = (x // (n - 1)) + 1
j = (x % (n - 1)) + 1
if i > j:
i, j = j, i
else:
j += 1
yield i, j
x = (x + d) % (n * (n - 1))
ans = 0
for i, j in make_query(*map(int, input().split())):
l = pos[i - 1]
r = pos[j - 1]
if l > r:
l, r = r, l
ans += seg.query(l, r)
print(ans)