結果

問題 No.1705 Mode of long array
ユーザー AEn
提出日時 2022-05-27 23:20:05
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 408 ms / 3,000 ms
コード長 3,643 bytes
コンパイル時間 437 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 109,056 KB
最終ジャッジ日時 2024-09-20 16:26:16
合計ジャッジ時間 18,059 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class SegmentTree():
# UnitXfinit
def __init__(self, init, unitX, f):
self.f = f # (X, X) -> X
self.unitX = unitX
self.f = f
if type(init) == int:
self.n = init
self.n = 1 << (self.n - 1).bit_length()
self.X = [unitX] * (self.n * 2)
else:
self.n = len(init)
self.n = 1 << (self.n - 1).bit_length()
# len(init)2UnitX
self.X = [unitX] * self.n + init + [unitX] * (self.n - len(init))
# index1
for i in range(self.n-1, 0, -1):
self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
# 0-indexedix
def update(self, i, x):
#
i += self.n
self.X[i] = x
#
i >>= 1
while i:
self.X[i] = self.f(self.X[i*2], self.X[i*2|1])
i >>= 1
# index
def getvalue(self, i):
return self.X[i + self.n]
# [l, r)f
def getrange(self, l, r):
l += self.n
r += self.n
al = self.unitX
ar = self.unitX
while l < r:
#
if l & 1:
al = self.f(al, self.X[l])
l += 1
#
if r & 1:
r -= 1
ar = self.f(self.X[r], ar)
l >>= 1
r >>= 1
return self.f(al, ar)
# Find r s.t. calc(l, ..., r-1) = True and calc(l, ..., r) = False
def max_right(self, l, z):
if l >= self.n: return self.n
l += self.n
s = self.unitX
while 1:
while l % 2 == 0:
l >>= 1
if not z(self.f(s, self.X[l])):
while l < self.n:
l *= 2
if z(self.f(s, self.X[l])):
s = self.f(s, self.X[l])
l += 1
return l - self.n
s = self.f(s, self.X[l])
l += 1
if l & -l == l: break
return self.n
# Find l s.t. calc(l, ..., r-1) = True and calc(l-1, ..., r-1) = False
def min_left(self, r, z):
if r <= 0: return 0
r += self.n
s = self.unitX
while 1:
r -= 1
while r > 1 and r % 2:
r >>= 1
if not z(self.f(self.X[r], s)):
while r < self.n:
r = r * 2 + 1
if z(self.f(self.X[r], s)):
s = self.f(self.X[r], s)
r -= 1
return r + 1 - self.n
s = self.f(self.X[r], s)
if r & -r == r: break
return 0
def debug(self):
print("debug")
print([self.getvalue(i) for i in range(min(self.n, 20))])
N, M = map(int, input().split())
A = list(map(int, input().split()))
def f(x, y):
n, p = x
n_, p_ = y
if n>n_:
return (n,p)
else:
return (n_,p_)
st = SegmentTree([(n, i) for i, n in enumerate(A)], (-1, -1), f)
Q = int(input())
for _ in range(Q):
t, a, b = map(int, input().split())
if t == 1:
n, p = st.getvalue(a-1)
st.update(a-1, (n+b, p))
elif t == 2:
n,p = st.getvalue(a-1)
st.update(a-1, (n-b, p))
else:
print(st.getrange(0, M)[1]+1)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0