結果
問題 | No.1705 Mode of long array |
ユーザー |
![]() |
提出日時 | 2021-10-11 01:00:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 299 ms / 3,000 ms |
コード長 | 2,071 bytes |
コンパイル時間 | 401 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 114,216 KB |
最終ジャッジ日時 | 2024-09-14 21:17:52 |
合計ジャッジ時間 | 15,072 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
class SegTree:def __init__(self, init_val, ide_ele, segfunc):self.n = len(init_val)self.num = 2**(self.n-1).bit_length()self.ide_ele = ide_eleself.segfunc = segfuncself.seg = [ide_ele]*2*self.num# set_valfor i in range(self.n):self.seg[i+self.num] = init_val[i]# builtfor i in range(self.num-1, 0, -1):self.seg[i] = self.segfunc(self.seg[2*i], self.seg[2*i+1])def update(self, k, x):k += self.numself.seg[k][0] += xwhile k:k = k >> 1self.seg[k] = self.segfunc(self.seg[2*k], self.seg[2*k+1])def query(self, l, r):if r <= l:return self.ide_elel += self.numr += self.numlres = self.ide_elerres = self.ide_elewhile l < r:if r & 1:r -= 1rres = self.segfunc(self.seg[r], rres)if l & 1:lres = self.segfunc(lres, self.seg[l])l += 1l = l >> 1r = r >> 1res = self.segfunc(lres, rres)return resdef __str__(self): # for debugarr = [self.query(i,i+1) for i in range(self.n)]return str(arr)def segfunc(x, y):if x[0] > y[0]:return xelif x[0] == y[0]:if x[1] > y[1]:return xelse:return yelse:return yimport sysimport io, osinput = io.BytesIO(os.read(0,os.fstat(0).st_size)).readlinedef main():n, m = map(int, input().split())A = list(map(int, input().split()))B = []for i, a in enumerate(A):B.append([a, i])seg = SegTree(B, [0, -1], segfunc)q = int(input())for i in range(q):t, x, y = map(int, input().split())x -= 1if t == 1:seg.update(x, y)elif t == 2:seg.update(x, -y)else:res = seg.query(0, seg.n)print(res[1]+1)if __name__ == '__main__':main()