結果

問題 No.1705 Mode of long array
コンテスト
ユーザー flippergo
提出日時 2025-04-02 22:26:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,288 bytes
コンパイル時間 436 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 122,284 KB
最終ジャッジ日時 2025-04-02 22:26:40
合計ジャッジ時間 20,018 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 24 WA * 27
権限があれば一括ダウンロードができます

ソースコード

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)]
A = list(map(int,input().split()))
for i in range(M):
    T[K+i] = [A[i],i+1]
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
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