結果

問題 No.3614 Breaking door keys（LITTLE BREAK ver.）
コンテスト
ユーザー flippergo
提出日時 2026-08-16 10:28:38
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,309 ms / 2,000 ms
+ 533µs
コード長 962 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 216 ms
コンパイル使用メモリ 95,844 KB
実行使用メモリ 353,704 KB
最終ジャッジ日時 2026-08-16 10:29:11
合計ジャッジ時間 28,649 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_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 

N,Q = map(int,input().split())
S = list(map(int,input().split()))
INFTY = 10**10
S = [INFTY]+S
A = [[] for _ in range(N+1)]
A[N] = [S[N]]
for i in range(N-1,0,-1):
    A[i] = A[i+1]+[S[i]]
    A[i] = sorted(A[i])
    if len(A[i])>10:
        A[i].pop()
K = 0
while 1<<K < N:
    K += 1
dp = [[[] for i in range(N+1)] for _ in range(K+1)]
for i in range(1,N+1):
    dp[0][i] = [S[i]]
for k in range(1,K+1):
    for i in range(1,N+1):
        if i+(1<<k)>N:
            dp[k][i] = A[i]
        else:
            dp[k][i] = dp[k-1][i]+dp[k-1][i+(1<<k-1)]
            dp[k][i] = sorted(dp[k][i])
            if len(dp[k][i])>10:
                dp[k][i] = dp[k][i][:10]
for _ in range(Q):
    L,R,M = map(int,input().split())
    R += 1
    d = R-L
    x = L
    B = []
    for i in range(K,-1,-1):
        if (d>>i) & 1:
            B += dp[i][x]
            B = sorted(B)
            if len(B)>M:
                B = B[:M]
            x += (1<<i)
    print(sum(B))
0