結果
問題 | No.1705 Mode of long array |
ユーザー |
![]() |
提出日時 | 2021-10-09 20:33:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 464 ms / 3,000 ms |
コード長 | 1,642 bytes |
コンパイル時間 | 175 ms |
コンパイル使用メモリ | 82,164 KB |
実行使用メモリ | 102,120 KB |
最終ジャッジ日時 | 2024-09-13 09:44:10 |
合計ジャッジ時間 | 18,956 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
class SegmentTree():def __init__(self, n, unit, f, A=None):self.s = 2**(n-1).bit_length()self.size = 2*self.sself.node = [unit]*self.sizeself.op = fself.UNIT = unitif A:for i in range(n):self.node[self.s+i] = A[i]for i in range(self.s-1, -1, -1):self.node[i] = self.op(self.node[2*i], self.node[2*i+1])def update(self, i, v):i += self.sself.node[i] = vwhile i > 0:i >>= 1self.node[i] = self.op(self.node[2*i], self.node[2*i+1])def get(self, l, r):vl, vr = self.UNIT, self.UNITl += self.sr += self.swhile l < r:if l & 1:vl = self.op(self.node[l], vl)l += 1if r & 1:r -= 1vr = self.op(vr, self.node[r])l >>= 1r >>= 1return self.op(vl, vr)def op(x, y):if x[0] < y[0]:return yelif x[0] > y[0]:return xelse:return x if x[1] > y[1] else yN, M = map(int, input().split())A = list(map(int, input().split()))B = [[0]*2 for _ in range(M+1)]for i in range(M):B[i+1] = [A[i], i+1]arr = SegmentTree(M+1, [0, 0], op, B)ans = []Q = int(input())for _ in range(Q):t, x, y = map(int, input().split())if t == 1:v = arr.get(x, x+1)[0]arr.update(x, [v+y, x])elif t == 2:v = arr.get(x, x+1)[0]arr.update(x, [v-y, x])else:z = arr.get(0, M+1)[1]ans.append(z)print(*ans, sep='\n')