結果

問題 No.3424 Shooting Game
コンテスト
ユーザー titia
提出日時 2026-01-16 03:52:29
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 390 ms / 2,000 ms
コード長 941 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 471 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 109,340 KB
最終ジャッジ日時 2026-01-16 03:52:35
合計ジャッジ時間 5,842 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

N,T=map(int,input().split())

A=[list(map(int,input().split())) for i in range(N)]

seg_el=1<<((500020+1).bit_length()) # Segment treeの台の要素数
SEG=[0]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

def getvalue(n,seg_el): # 一点の値を取得
    i=n+seg_el
    ANS=0
    
    ANS=max(SEG[i],ANS)
    i>>=1# 子ノードへ
    
    while i!=0:
        ANS=max(SEG[i],ANS)
        i>>=1

    return ANS

def updates(l,r,x): # 区間[l,r)のminを更新.
    L=l+seg_el
    R=r+seg_el

    while L<R:
        if L & 1:
            SEG[L]=max(x,SEG[L])
            L+=1

        if R & 1:
            R-=1
            SEG[R]=max(x,SEG[R])
        L>>=1
        R>>=1

for l,r,p in A:
    updates(l,r+1,p)

DP=[0]*500020

for i in range(200020):
    x=getvalue(i,seg_el)
    DP[i]=max(DP[i],DP[i-1])
    DP[i+T]=max(DP[i+T],DP[i]+x)

print(max(DP))
0