結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー ainem-m
提出日時 2022-05-12 09:23:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,717 ms / 5,000 ms
コード長 3,185 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 179,380 KB
最終ジャッジ日時 2024-07-20 01:43:39
合計ジャッジ時間 12,222 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

class Monoid:
  def __init__(self, ope, e):
    self.ope = ope
    self.e = e

class Mapping:
  def __init__(self, ope, composition, id):
    self.ope = ope
    self.composition = composition
    self.id = id

class LazySegTree:
  def __init__(self, monoid, mapping, n=0, array=None):
    assert (n>0 and array is None) or (n==0 and array), 'Only either n(int) or array(list) can be passed'
    self.X_ope = monoid.ope
    self.X_e = monoid.e
    self.A_ope = mapping.ope
    self.A_comp = mapping.composition
    self.A_id = mapping.id
    self.n = n if n else len(array)
    self.X = [self.X_e] * (2*self.n)
    self.A = [self.A_id] * (2*self.n)
    if array:
      self.X[self.n:2*self.n] = array
      for i in range(1, self.n)[::-1]:
        self.X[i] = self.X_ope(self.X[i<<1|0], self.X[i<<1|1])
  
  def _first_odd(self, i):
    return i // (i & -i)
  
  def _eval(self, i):
    return self.A_ope(self.X[i], self.A[i])
  
  def _propagate(self,i):
    self.X[i] = self._eval(i)
    self.A[i<<1|0] = self.A_comp(self.A[i<<1|0], self.A[i])
    self.A[i<<1|1] = self.A_comp(self.A[i<<1|1], self.A[i])
    self.A[i] = self.A_id
    
  def _propagate_above(self, i):
    H = i.bit_length() - 1
    for h in range(1, H+1)[::-1]:
      self._propagate(i >> h)
  
  def _recalc_above(self, i):
    while i>1:
      i >>= 1
      self.X[i] = self.X_ope(self._eval(i<<1|0), self._eval(i<<1|1))
  
  def set(self, i, x):
    i += self.n
    self._propagate_above(i)
    self.X[i] = x
    self.A[i] = self.A_id
    self._recalc_above(i)
  
  def get(self, l, r):
    l += self.n; r += self.n
    self._propagate_above(self._first_odd(l))
    self._propagate_above(self._first_odd(r)-1)
    value_l = self.X_e
    value_r = self.X_e
    while l<r:
      if l & 1:
        value_l = self.X_ope(value_l, self._eval(l))
        l += 1
      if r & 1:
        r -= 1
        value_r = self.X_ope(self._eval(r), value_r)
      l >>= 1; r >>= 1
    return self.X_ope(value_l, value_r)
  
  def operate_range(self, l, r, a):
    l += self.n; r += self.n
    l0 = self._first_odd(l)
    r0 = self._first_odd(r)-1
    self._propagate_above(l0)
    self._propagate_above(r0)
    while l < r:
      if l & 1:
        self.A[l] = self.A_comp(self.A[l], a)
        l += 1
      if r & 1:
        r -= 1
        self.A[r] = self.A_comp(self.A[r], a)
      l >>= 1; r >>= 1
    self._recalc_above(l0)
    self._recalc_above(r0)
  
  
def color_sum(x1, x2):
  a1, a2, a3 = x1
  b1, b2, b3 = x2
  return (a1+b1, a2+b2, a3+b3)

def paint_comp(a1, a2):
  return a2 if a2 else a1

def paint(x, a):
  if not a: return x
  elif a == 1: return (0, sum(x), 0)
  elif a == 2: return (0, 0, sum(x))

monoid = Monoid(color_sum, (0,0,0))
mapping = Mapping(paint, paint_comp, 0)

n = int(input())
q = int(input())

score_A = 0
score_B = 0

seg = LazySegTree(monoid, mapping, array=[(1, 0, 0)]*n)

for qi in range(q):
  x, l, r = map(int, input().split())
  if x == 0:
    _, a, b = seg.get(l, r+1)
    if a > b:
      score_A += a
    elif b > a:
      score_B += b
    else:
      pass
  else:
    seg.operate_range(l, r+1, x)

_, a, b = seg.get(0, n)
print(score_A+a, score_B+b)
0