結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー ainem-mainem-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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
52,864 KB
testcase_01 AC 39 ms
52,608 KB
testcase_02 AC 38 ms
52,608 KB
testcase_03 AC 37 ms
52,480 KB
testcase_04 AC 39 ms
52,608 KB
testcase_05 AC 176 ms
78,152 KB
testcase_06 AC 333 ms
82,372 KB
testcase_07 AC 153 ms
77,876 KB
testcase_08 AC 235 ms
78,988 KB
testcase_09 AC 933 ms
122,724 KB
testcase_10 AC 736 ms
84,940 KB
testcase_11 AC 702 ms
105,552 KB
testcase_12 AC 944 ms
122,144 KB
testcase_13 AC 391 ms
85,812 KB
testcase_14 AC 323 ms
91,652 KB
testcase_15 AC 803 ms
97,200 KB
testcase_16 AC 1,093 ms
138,544 KB
testcase_17 AC 1,717 ms
179,380 KB
testcase_18 AC 485 ms
104,492 KB
testcase_19 AC 1,245 ms
148,024 KB
権限があれば一括ダウンロードができます

ソースコード

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