結果
| 問題 |
No.2162 Copy and Paste 2
|
| コンテスト | |
| ユーザー |
 miscalc
|
| 提出日時 | 2021-08-26 04:32:25 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 5,512 ms / 7,000 ms |
| コード長 | 6,828 bytes |
| コンパイル時間 | 484 ms |
| コンパイル使用メモリ | 82,304 KB |
| 実行使用メモリ | 107,688 KB |
| 最終ジャッジ日時 | 2024-11-06 21:06:24 |
| 合計ジャッジ時間 | 82,887 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 26 |
ソースコード
# ACL-for-python by shakayami
# https://github.com/shakayami/ACL-for-python
class string:
def z_algorithm(s):
n = len(s)
if n == 0:
return []
z = [0]*n
i = 1
j = 0
while(i < n):
z[i] = 0 if (j+z[j] <= i) else min(j+z[j]-i, z[i-j])
while((i+z[i] < n) and (s[z[i]] == s[i+z[i]])):
z[i] += 1
if (j+z[j] < i+z[i]):
j = i
i += 1
z[0] = n
return z
class lazy_segtree():
def update(self, k): self.d[k] = self.op(self.d[2*k], self.d[2*k+1])
def all_apply(self, k, f):
self.d[k] = self.mapping(f, self.d[k])
if (k < self.size):
self.lz[k] = self.composition(f, self.lz[k])
def push(self, k):
self.all_apply(2*k, self.lz[k])
self.all_apply(2*k+1, self.lz[k])
self.lz[k] = self.identity
def __init__(self, V, OP, E, MAPPING, COMPOSITION, ID):
self.n = len(V)
self.log = (self.n-1).bit_length()
self.size = 1 << self.log
self.d = [E for i in range(2*self.size)]
self.lz = [ID for i in range(self.size)]
self.e = E
self.op = OP
self.mapping = MAPPING
self.composition = COMPOSITION
self.identity = ID
for i in range(self.n):
self.d[self.size+i] = V[i]
for i in range(self.size-1, 0, -1):
self.update(i)
def set(self, p, x):
assert 0 <= p and p < self.n
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
self.d[p] = x
for i in range(1, self.log+1):
self.update(p >> i)
def get(self, p):
assert 0 <= p and p < self.n
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
return self.d[p]
def prod(self, l, r):
assert 0 <= l and l <= r and r <= self.n
if l == r:
return self.e
l += self.size
r += self.size
for i in range(self.log, 0, -1):
if (((l >> i) << i) != l):
self.push(l >> i)
if (((r >> i) << i) != r):
self.push(r >> i)
sml, smr = self.e, self.e
while(l < r):
if l & 1:
sml = self.op(sml, self.d[l])
l += 1
if r & 1:
r -= 1
smr = self.op(self.d[r], smr)
l >>= 1
r >>= 1
return self.op(sml, smr)
def all_prod(self): return self.d[1]
def apply_point(self, p, f):
assert 0 <= p and p < self.n
p += self.size
for i in range(self.log, 0, -1):
self.push(p >> i)
self.d[p] = self.mapping(f, self.d[p])
for i in range(1, self.log+1):
self.update(p >> i)
def apply(self, l, r, f):
assert 0 <= l and l <= r and r <= self.n
if l == r:
return
l += self.size
r += self.size
for i in range(self.log, 0, -1):
if (((l >> i) << i) != l):
self.push(l >> i)
if (((r >> i) << i) != r):
self.push((r-1) >> i)
l2, r2 = l, r
while(l < r):
if (l & 1):
self.all_apply(l, f)
l += 1
if (r & 1):
r -= 1
self.all_apply(r, f)
l >>= 1
r >>= 1
l, r = l2, r2
for i in range(1, self.log+1):
if (((l >> i) << i) != l):
self.update(l >> i)
if (((r >> i) << i) != r):
self.update((r-1) >> i)
def max_right(self, l, g):
assert 0 <= l and l <= self.n
assert g(self.e)
if l == self.n:
return self.n
l += self.size
for i in range(self.log, 0, -1):
self.push(l >> i)
sm = self.e
while(1):
while(i % 2 == 0):
l >>= 1
if not(g(self.op(sm, self.d[l]))):
while(l < self.size):
self.push(l)
l = (2*l)
if (g(self.op(sm, self.d[l]))):
sm = self.op(sm, self.d[l])
l += 1
return l-self.size
sm = self.op(sm, self.d[l])
l += 1
if (l & -l) == l:
break
return self.n
def min_left(self, r, g):
assert (0 <= r and r <= self.n)
assert g(self.e)
if r == 0:
return 0
r += self.size
for i in range(self.log, 0, -1):
self.push((r-1) >> i)
sm = self.e
while(1):
r -= 1
while(r > 1 and (r % 2)):
r >>= 1
if not(g(self.op(self.d[r], sm))):
while(r < self.size):
self.push(r)
r = (2*r+1)
if g(self.op(self.d[r], sm)):
sm = self.op(self.d[r], sm)
r -= 1
return r+1-self.size
sm = self.op(self.d[r], sm)
if (r & -r) == r:
break
return 0
class fenwick_tree():
n = 1
data = [0 for i in range(n)]
def __init__(self, N):
self.n = N
self.data = [0 for i in range(N)]
def add(self, p, x):
assert 0 <= p < self.n, "0<=p<n,p={0},n={1}".format(p, self.n)
p += 1
while(p <= self.n):
self.data[p-1] += x
p += p & -p
def sum(self, l, r):
assert (0 <= l and l <= r and r <=
self.n), "0<=l<=r<=n,l={0},r={1},n={2}".format(l, r, self.n)
return self.sum0(r)-self.sum0(l)
def sum0(self, r):
s = 0
while(r > 0):
s += self.data[r-1]
r -= r & -r
return s
def lower_bound(self, w):
if w < 0:
return -1
k = 1
while k < self.n:
k <<= 1
x = 0
ww = w
while k > 0:
if x + k - 1 < self.n and self.data[x + k - 1] < ww:
ww -= self.data[x + k - 1]
x += k
k >>= 1
return x
s = input()
n = len(s)
z = string.z_algorithm(s)
for i in range(n):
z[i] = min(z[i], i)
invz = [[] for i in range(n)]
fw = fenwick_tree(n + 2)
for i in range(n):
if z[i] >= 2:
invz[z[i]].append(i)
fw.add(i, 1)
fw.add(n + 1, 1)
def op(a, b):
return max(a, b)
dp = lazy_segtree([0 for i in range(n + 1)], op, 0, op, op, 0)
for j in range(2, n):
cnt = dp.get(j) + j - 2
i = fw.lower_bound(1) + j
while i < n + 1:
dp.apply(i, n + 1, cnt)
cnt += j - 1
i = fw.lower_bound(fw.sum0(i) + 1) + j
for ii in invz[j]:
fw.add(ii, -1)
ans = n - dp.get(n)
print(ans)