結果

問題 No.2162 Copy and Paste 2
ユーザー miscalcmiscalc
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 46 ms
54,400 KB
testcase_01 AC 47 ms
54,400 KB
testcase_02 AC 46 ms
54,912 KB
testcase_03 AC 41 ms
53,632 KB
testcase_04 AC 41 ms
53,632 KB
testcase_05 AC 40 ms
53,888 KB
testcase_06 AC 1,013 ms
100,008 KB
testcase_07 AC 1,025 ms
99,824 KB
testcase_08 AC 2,227 ms
103,676 KB
testcase_09 AC 2,446 ms
100,992 KB
testcase_10 AC 2,600 ms
98,972 KB
testcase_11 AC 2,961 ms
102,252 KB
testcase_12 AC 3,346 ms
101,968 KB
testcase_13 AC 4,264 ms
105,436 KB
testcase_14 AC 2,561 ms
100,092 KB
testcase_15 AC 2,551 ms
100,292 KB
testcase_16 AC 2,761 ms
100,212 KB
testcase_17 AC 4,125 ms
104,300 KB
testcase_18 AC 5,098 ms
106,444 KB
testcase_19 AC 5,451 ms
104,324 KB
testcase_20 AC 4,717 ms
104,248 KB
testcase_21 AC 2,946 ms
104,624 KB
testcase_22 AC 2,756 ms
103,504 KB
testcase_23 AC 245 ms
95,548 KB
testcase_24 AC 5,251 ms
105,476 KB
testcase_25 AC 5,241 ms
107,688 KB
testcase_26 AC 5,294 ms
106,052 KB
testcase_27 AC 5,284 ms
107,016 KB
testcase_28 AC 5,512 ms
102,576 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 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)
0