ABC340Eを解いた

筆者はAtCoderのレート600弱の茶色コーダ

ADTで解けなかった問題を復習する。

ADTのページ

実装コード

遅延セグ木をつかえばいけるらしい

遅延セグ木の実装は以下のものを使用した

• shakayami/ACL-for-python

import sys
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)
class lazy_segtree():
    # --- 中略 ---

def op(ele1, ele2):
    return ele1 + ele2
def mapping(func, ele):
    return func + ele
def composition(func_upper, func_lower):
    return func_upper + func_lower

e = 0
id_ = 0

def main():
    N, M = rLI()
    A = rLI()
    B = rLI()
    
    G=lazy_segtree(A,op, e,mapping,composition,id_)
    
    for b in B:
        x = G.get(b)
        G.set(b,0)
        k,y = divmod(x,N)
        G.apply(0,N,k)
        if b+y >= N:
            G.apply(b+1, N, 1)
            G.apply(0, b+y-N+1, 1)
        else:
            G.apply(b+1, b+y+1, 1)
    print(" ".join([str(G.get(p)) for p in range(G.n)]))
    
    
if __name__ == '__main__':
    main()

まとめ

遅延セグ木を使ってABC340Eを解いた

余談

この問題解いたら寝よー
とか思っていたらドはまりして2時間ぐらい消費した😢

諦めて一回寝たら解けたので、
行き詰ったら一回寝ましょう。