結果
| 問題 | No.2992 Range ABCD String Query |
| ユーザー |
 nikoro256
|
| 提出日時 | 2024-12-17 01:09:05 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 5,748 ms / 6,000 ms |
| コード長 | 4,767 bytes |
| コンパイル時間 | 489 ms |
| コンパイル使用メモリ | 82,380 KB |
| 実行使用メモリ | 273,240 KB |
| 最終ジャッジ日時 | 2024-12-17 01:12:27 |
| 合計ジャッジ時間 | 151,409 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1,059 ms
82,100 KB |
| testcase_01 | AC | 1,060 ms
82,376 KB |
| testcase_02 | AC | 1,396 ms
83,940 KB |
| testcase_03 | AC | 1,234 ms
82,800 KB |
| testcase_04 | AC | 1,526 ms
84,508 KB |
| testcase_05 | AC | 1,128 ms
83,324 KB |
| testcase_06 | AC | 1,374 ms
83,372 KB |
| testcase_07 | AC | 804 ms
82,140 KB |
| testcase_08 | AC | 1,543 ms
85,048 KB |
| testcase_09 | AC | 1,250 ms
82,224 KB |
| testcase_10 | AC | 4,958 ms
268,996 KB |
| testcase_11 | AC | 5,082 ms
268,916 KB |
| testcase_12 | AC | 5,235 ms
269,476 KB |
| testcase_13 | AC | 5,270 ms
268,860 KB |
| testcase_14 | AC | 4,876 ms
269,356 KB |
| testcase_15 | AC | 5,137 ms
269,528 KB |
| testcase_16 | AC | 4,977 ms
266,756 KB |
| testcase_17 | AC | 5,073 ms
268,832 KB |
| testcase_18 | AC | 5,538 ms
269,000 KB |
| testcase_19 | AC | 5,300 ms
268,628 KB |
| testcase_20 | AC | 3,835 ms
269,908 KB |
| testcase_21 | AC | 4,253 ms
270,124 KB |
| testcase_22 | AC | 3,655 ms
269,752 KB |
| testcase_23 | AC | 3,978 ms
269,408 KB |
| testcase_24 | AC | 3,733 ms
270,200 KB |
| testcase_25 | AC | 5,146 ms
273,116 KB |
| testcase_26 | AC | 5,748 ms
273,112 KB |
| testcase_27 | AC | 5,082 ms
273,104 KB |
| testcase_28 | AC | 5,671 ms
273,240 KB |
| testcase_29 | AC | 5,112 ms
272,696 KB |
| testcase_30 | AC | 4,432 ms
210,876 KB |
| testcase_31 | AC | 5,132 ms
210,496 KB |
| testcase_32 | AC | 4,888 ms
210,232 KB |
| testcase_33 | AC | 5,338 ms
210,864 KB |
| testcase_34 | AC | 4,927 ms
211,356 KB |
| testcase_35 | AC | 4,578 ms
147,692 KB |
| testcase_36 | AC | 4,682 ms
147,208 KB |
| testcase_37 | AC | 564 ms
79,880 KB |
| testcase_38 | AC | 749 ms
82,012 KB |
| testcase_39 | AC | 837 ms
82,672 KB |
| testcase_40 | AC | 893 ms
82,220 KB |
ソースコード
import typing
def _ceil_pow2(n: int) -> int:
x = 0
while (1 << x) < n:
x += 1
return x
def _bsf(n: int) -> int:
x = 0
while n % 2 == 0:
x += 1
n //= 2
return x
class SegTree:
def __init__(self,
op: typing.Callable[[typing.Any, typing.Any], typing.Any],
e: typing.Any,
v: typing.Union[int, typing.List[typing.Any]]) -> None:
self._op = op
self._e = e
if isinstance(v, int):
v = [e] * v
self._n = len(v)
self._log = _ceil_pow2(self._n)
self._size = 1 << self._log
self._d = [e] * (2 * self._size)
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: int, x: typing.Any) -> None:
assert 0 <= p < self._n
p += self._size
self._d[p] = x
for i in range(1, self._log + 1):
self._update(p >> i)
def get(self, p: int) -> typing.Any:
assert 0 <= p < self._n
return self._d[p + self._size]
def prod(self, left: int, right: int) -> typing.Any:
assert 0 <= left <= right <= self._n
sml = self._e
smr = self._e
left += self._size
right += self._size
while left < right:
if left & 1:
sml = self._op(sml, self._d[left])
left += 1
if right & 1:
right -= 1
smr = self._op(self._d[right], smr)
left >>= 1
right >>= 1
return self._op(sml, smr)
def all_prod(self) -> typing.Any:
return self._d[1]
def max_right(self, left: int,
f: typing.Callable[[typing.Any], bool]) -> int:
assert 0 <= left <= self._n
assert f(self._e)
if left == self._n:
return self._n
left += self._size
sm = self._e
first = True
while first or (left & -left) != left:
first = False
while left % 2 == 0:
left >>= 1
if not f(self._op(sm, self._d[left])):
while left < self._size:
left *= 2
if f(self._op(sm, self._d[left])):
sm = self._op(sm, self._d[left])
left += 1
return left - self._size
sm = self._op(sm, self._d[left])
left += 1
return self._n
def min_left(self, right: int,
f: typing.Callable[[typing.Any], bool]) -> int:
assert 0 <= right <= self._n
assert f(self._e)
if right == 0:
return 0
right += self._size
sm = self._e
first = True
while first or (right & -right) != right:
first = False
right -= 1
while right > 1 and right % 2:
right >>= 1
if not f(self._op(self._d[right], sm)):
while right < self._size:
right = 2 * right + 1
if f(self._op(self._d[right], sm)):
sm = self._op(self._d[right], sm)
right -= 1
return right + 1 - self._size
sm = self._op(self._d[right], sm)
return 0
def _update(self, k: int) -> None:
self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])
N,Q=map(int,input().split())
S=input()
S=list(S)
"""
a
b
c
d
ab
bc
cd
da
abc
bcd
d
"""
change = []
for i in range(4):
for j in range(4):
if j + i < 4:
change.append((j,j+i))
move = []
for k in range(len(change)):
for t in range(len(change)):
if change[k][1] <= change[t][0]:
new = (change[k][0],change[t][1])
move.append((k,t,change.index(new)))
s = "ABCD"
def one(n):
count = 0
res = []
for i in range(4):
for j in range(4):
if j + i < 4:
count += 1
if j <= n <= j+i:
res.append(0)
else:
res.append(1)
return tuple(res)
ones = [one(i) for i in range(4)]
inf = 10**6
def op(a,b):
new = [inf for _ in range(10)]
for a_,b_,c in move:
new[c] =min(new[c], a[a_]+b[b_])
return tuple(new)
st = SegTree(op=lambda a,b:op(a,b),e=tuple(0 for _ in range(10)),v=[ones[s.index(S[i])] for i in range(N)])
for _ in range(Q):
q=list(map(str,input().split()))
if q[0] == "1":
_,x,c = q
x=int(x)
st.set(x-1,ones[s.index(c)])
else:
_,l,r = q
l=int(l)
r=int(r)
ans=st.prod(l-1,r)
print(min(ans))