結果

問題 No.3017 交互浴
ユーザー nasutarou1341
提出日時 2025-01-25 14:33:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,005 ms / 2,000 ms
コード長 3,730 bytes
コンパイル時間 325 ms
コンパイル使用メモリ 82,568 KB
実行使用メモリ 126,312 KB
最終ジャッジ日時 2025-01-25 23:23:41
合計ジャッジ時間 44,733 ms
ジャッジサーバーID
（参考情報） 		judge8 / judge11
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

class segtree:
  #セグメント木
  def __init__(s, v, op, e):
    s._n = len(v)
    s.log = s.ceil_pow2(s._n)
    s.size = 1 << s.log
    s.d = [e()] * (2 * s.size)
    s.e = e
    s.op = op
    for i in range(s._n): s.d[s.size + i] = v[i]
    for i in range(s.size - 1, 0, -1): s.update(i)
  
  # 1点更新
  def set(s, p, x):
    p += s.size
    s.d[p] = x
    for i in range(1, s.log + 1): s.update(p >> i)
 
  # 1点取得
  def get(s, p):
    return s.d[p + s.size]
 
  # 区間演算
  def prod(s, l, r):
    sml, smr = s.e(), s.e()
    l += s.size
    r += s.size
    while (l < r):
      if l & 1: 
        sml = s.op(sml, s.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = s.op(s.d[r], smr)
      l >>= 1
      r >>= 1
    return s.op(sml, smr)
 
  # 全体演算
  def all_prod(s): return s.d[1]
 
  # L固定時の最長区間のR
  def max_right(s, l, g):
    if l == s._n: return s._n
    l += s.size
    sm = s.e()
    while True:
      while (l % 2 == 0): l >>= 1
      if not g(s.op(sm, s.d[l])):
        while l < s.size:
          l = 2 * l
          if g(s.op(sm, s.d[l])):
            sm = s.op(sm, s.d[l])
            l += 1
        return l - s.size
      sm = s.op(sm, s.d[l])
      l += 1
      if (l & -l) == l: break
    return s._n
 
  # R固定時の最長区間のL
  def min_left(s, r, g):
    if r == 0: return 0
    r += s.size
    sm = s.e()
    while True:
      r -= 1
      while r > 1 and (r % 2): r >>= 1
      if not g(s.op(s.d[r], sm)):
        while r < s.size:
          r = 2 * r + 1
          if g(s.op(s.d[r], sm)):
            sm = s.op(s.d[r], sm)
            r -= 1
        return r + 1 - s.size
      sm = s.op(s.d[r], sm)
      if (r & - r) == r: break
    return 0
 
  def update(s, k): s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])
  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x
  def print(s): #デバッグ用
    ans = []
    for i in range(s._n):
      ans.append(s.get(i))
    print(*ans)
  
class segtreeFactory:
  MAX_INT = 10 ** 18
  MOD = 998244353
  # サイズNのmaxSegTree
  @staticmethod
  def makeMaxSegTree(N,  v = None):
    if v == None: v = [0] * N
    return segtree(v, segtreeFactory.opmax, segtreeFactory.emax)
  # サイズNのminSegTree
  @staticmethod
  def makeMinSegTree(N, v = None):
    if v == None: v = [segtreeFactory.MAX_INT] * N
    return segtree(v, segtreeFactory.opmin, segtreeFactory.emin)
  # サイズNのsumSegTree
  @staticmethod
  def makeSumSegTree(N, v = None):
    if v == None: v = [0] * N
    return segtree(v, segtreeFactory.opsum, segtreeFactory.emax)
  # サイズNのfuncSegTree (一次関数の結合)
  @staticmethod
  def makeFuncSegTree(N, v = None):
    if v == None: v = [[1, 0] for _ in range(N)]
    return segtree(v, segtreeFactory.opfunc, segtreeFactory.efunc)
  @staticmethod
  def emax(): return -1
  @staticmethod
  def opmax(s, t): return max(s, t)
  @staticmethod
  def emin(): return segtreeFactory.MAX_INT
  @staticmethod
  def opmin(s, t): return min(s, t)
  @staticmethod
  def opsum(s, t): return s + t
  @staticmethod
  def efunc(): return [1, 0]
  @staticmethod
  def opfunc(s, t): return [s[0] * t[0] % segtreeFactory.MOD, (t[0] * s[1] + t[1]) % segtreeFactory.MOD] # 左を内側にして結合

N = int(input())
H = list(map(int, input().split()))

ans = [0] * N

v = [-1] * N
seg = segtreeFactory.makeMaxSegTree(N, v)
H = [[H[i], i] for i in range(N)]
H.sort(reverse = True)

for i in range(N):
  h, n = H[i]
  m = seg.prod(0, n)
  if m == -1:
    a = 0
    if n % 2 == 0:
      a += h
  else:
    a = ans[m]
    if n % 2 != m % 2:
      if n % 2 == 0:
        a += h
      else:
        a -= h
  ans[n] = a
  seg.set(n, n)

for d in ans:
  print(d)
0