結果

問題 No.1705 Mode of long array
ユーザー kept1994
提出日時 2022-05-01 12:35:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 412 ms / 3,000 ms
コード長 2,614 bytes
コンパイル時間 151 ms
コンパイル使用メモリ 82,252 KB
実行使用メモリ 103,860 KB
最終ジャッジ日時 2024-06-30 14:55:55
合計ジャッジ時間 18,691 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

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

#!/usr/bin/env python3
import sys
MOD = 998244353
class SegTree:
def __init__(self, monoid, bottomList, func):
self.monoid = monoid
self.func = func
self.bottomLen = len(bottomList)
self.offset = self.bottomLen #
self.segLen = self.bottomLen * 2
self.tree = [monoid] * self.segLen
self.build(bottomList)
"""
O(self.segLen)
"""
def build(self, seq):
#
for i, x in enumerate(seq, self.offset):
self.tree[i] = x
#
for i in range(self.offset - 1, 0, -1):
self.tree[i] = self.func(self.tree[i << 1], self.tree[i << 1 | 1])
"""
O(log(self.bottomLen))
"""
def pointUpdate(self, i: int, val: int):
i += self.offset
self.tree[i] = val
while i > 1:
i >>= 1 # 2
self.tree[i] = self.func(self.tree[i << 1], self.tree[i << 1 | 1]) # 01or
"""
O(log(self.bottomLen))
"""
def getRange(self, l: int, r: int): # r
l += self.offset
r += self.offset
vL = (self.monoid, 0)
vR = (self.monoid, 0)
while l < r:
if l & 1:
vL = self.func(vL, self.tree[l])
l += 1
if r & 1:
r -= 1
vR = self.func(self.tree[r], vR)
l >>= 1
r >>= 1
return self.func(vL, vR)
"""
O(log(self.bottomLen))
"""
def getPoint(self, i: int):
i += self.offset
return self.tree[i]
def f(x: tuple, y: tuple):
if x[0] > y[0]:
return x
elif x[0] == y[0]:
if x[1] > y[1]:
return x
else:
return y
else:
return y
def main():
N, M = map(int, input().split())
A = list(map(int, input().split()))
Q = int(input())
seg = SegTree(0, [(aa, i) for i, aa in enumerate(A)], f)
for _ in range(Q):
t, x, y = list(map(int, input().split()))
if t == 1:
num, _ = seg.getPoint(x - 1)
seg.pointUpdate(x - 1, (num + y, x - 1))
elif t == 2:
num, _ = seg.getPoint(x - 1)
seg.pointUpdate(x - 1, (num - y, x - 1))
else:
print((seg.getRange(0, M))[1] + 1)
return
if __name__ == '__main__':
main()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0