結果

問題 No.1705 Mode of long array
ユーザー flippergo
提出日時 2025-04-02 22:36:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 537 ms / 3,000 ms
コード長 1,328 bytes
コンパイル時間 400 ms
コンパイル使用メモリ 82,768 KB
実行使用メモリ 117,820 KB
最終ジャッジ日時 2025-04-02 22:37:06
合計ジャッジ時間 21,521 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,M = map(int,input().split())
k = 0
while 2**k<M:
    k += 1
K = 2**k  # ノード数
T = [[0,0] for _ in range(2*K)]
for i in range(1,M+1):
    T[i+K-1][1] = i
A = list(map(int,input().split()))
def update(i,x):  # 更新
    i += K-1
    T[i] = [T[i][0]+x,T[i][1]]
    i = i//2
    while i>0:
        if T[2*i][0]<=T[2*i+1][0]:
            T[i] = T[2*i+1]
        else:
            T[i] = T[2*i]
        i //= 2
def find(l,r):  # 区間最大値
    l += K-1  # 左側の頂点
    r += K-1  # 右側の頂点
    res = [0,0]
    while l<r:
        if l&1:  # 右子の場合
            if res[0]<T[l][0]:
                res = T[l]
            elif res[0]==T[l][0] and T[l][1]>res[1]:
                res = T[l]
            l += 1  # 右隣の頂点に移る
        if r&1:  # &0としたいところだが、この操作は意味ない
            r -= 1  # 左隣の頂点に移る
            if res[0]<T[r][0]:
                res = T[r]
            elif res[0]==T[r][0] and T[r][1]>res[1]:
                res = T[r]
        l >>= 1  # 親に移る
        r >>= 1  # 親に移る
    return res
for i in range(M):
    update(i+1,A[i])
Q = int(input())
for _ in range(Q):
    t,x,y = map(int,input().split())
    if t==1:
        update(x,y)
    elif t==2:
        update(x,-y)
    else:
        print(find(1,M+1)[1])
0