結果

問題 No.3614 Breaking door keys（LITTLE BREAK ver.）
コンテスト
ユーザー hiryuN
提出日時 2026-08-06 16:20:47
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,201 ms / 2,000 ms
+ 560µs
コード長 1,421 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 746 ms
コンパイル使用メモリ 95,976 KB
実行使用メモリ 127,628 KB
最終ジャッジ日時 2026-08-06 16:21:20
合計ジャッジ時間 28,425 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
サンプル 0 % AC * 3
小課題1 10 % AC * 7
小課題2 20 % AC * 7
小課題3 30 % AC * 7
小課題4 30 % AC * 14
小課題5 10 % AC * 38
合計 2.5 * 100% = 250 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#セグメント木
#　2**segsize が 配列の長さを超えるように
segsize=18
# 単位元
ident=[10**18]*10
# 用いる関数
def seg_f(X,Y):
    Ans=[]
    xp=0
    yp=0
    for i in range(10):
        if X[xp]<Y[yp]:
            Ans.append(X[xp])
            xp+=1
        else:
            Ans.append(Y[yp])
            yp+=1
    return Ans
        

Seg=[]
for i in range(segsize+1):
    Seg.append([ident]*(2**i))

def seg_add(key,num):
    Seg[-1][key]=seg_f(Seg[-1][key],num)
    seg_indd(key,segsize)

def seg_paste(key,num):
    Seg[-1][key]=num
    seg_indd(key,segsize)

def seg_indd(key,rank):
    if rank!=0:
        key=key//2*2
        Seg[rank-1][key//2]=seg_f(Seg[rank][key],Seg[rank][key^1])
        seg_indd(key//2,rank-1)

def seg_deel(A):
    for i in range(len(A)):
        seg_paste(i,A[i])


def seg_get(l,r=None):
    if r==None:
        r=l+1
    ansl=ident
    ansr=ident
    rank=segsize
    while rank>=0 and r!=l:
        if l%2==1:
            ansl=seg_f(ansl,Seg[rank][l])
            l+=1
        if r%2==1:
            ansr=seg_f(Seg[rank][r-1],ansr)
            r-=1
        l//=2
        r//=2
        rank-=1
    return seg_f(ansl,ansr)

n,Q=map(int,input().split())
A=list(map(int,input().split()))
for i in range(n):
    seg_paste(i+1,[A[i]]+[10**18]*9)


for i in range(Q):
    a,b,c=map(int,input().split())
    Ans=seg_get(a,b+1)
    #print(Ans)
    print(sum(Ans[:c]))
0