結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー ainem-mainem-m
提出日時 2022-05-12 09:23:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,733 ms / 5,000 ms
コード長 3,185 bytes
コンパイル時間 1,313 ms
コンパイル使用メモリ 87,312 KB
実行使用メモリ 183,280 KB
最終ジャッジ日時 2023-09-27 07:35:17
合計ジャッジ時間 14,202 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 65 ms
71,336 KB
testcase_01 AC 66 ms
71,616 KB
testcase_02 AC 65 ms
71,344 KB
testcase_03 AC 64 ms
71,332 KB
testcase_04 AC 65 ms
71,340 KB
testcase_05 AC 210 ms
80,056 KB
testcase_06 AC 374 ms
85,596 KB
testcase_07 AC 175 ms
79,316 KB
testcase_08 AC 263 ms
83,688 KB
testcase_09 AC 977 ms
125,796 KB
testcase_10 AC 781 ms
87,884 KB
testcase_11 AC 746 ms
111,724 KB
testcase_12 AC 965 ms
125,456 KB
testcase_13 AC 427 ms
89,040 KB
testcase_14 AC 334 ms
92,864 KB
testcase_15 AC 830 ms
100,336 KB
testcase_16 AC 1,165 ms
142,400 KB
testcase_17 AC 1,733 ms
183,280 KB
testcase_18 AC 528 ms
105,296 KB
testcase_19 AC 1,298 ms
152,288 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