結果

問題 No.2879 Range Flip Queries
ユーザー YuuuTYuuuT
提出日時 2024-09-08 13:10:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,623 ms / 2,000 ms
コード長 5,892 bytes
コンパイル時間 214 ms
コンパイル使用メモリ 82,464 KB
実行使用メモリ 163,800 KB
最終ジャッジ日時 2024-09-08 13:11:01
合計ジャッジ時間 31,028 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
56,756 KB
testcase_01 AC 43 ms
57,256 KB
testcase_02 AC 45 ms
56,340 KB
testcase_03 AC 189 ms
76,544 KB
testcase_04 AC 187 ms
76,480 KB
testcase_05 AC 255 ms
77,220 KB
testcase_06 AC 326 ms
77,900 KB
testcase_07 AC 333 ms
77,884 KB
testcase_08 AC 91 ms
76,780 KB
testcase_09 AC 62 ms
70,184 KB
testcase_10 AC 86 ms
76,608 KB
testcase_11 AC 98 ms
76,756 KB
testcase_12 AC 97 ms
76,744 KB
testcase_13 AC 1,235 ms
123,452 KB
testcase_14 AC 1,312 ms
127,120 KB
testcase_15 AC 836 ms
102,612 KB
testcase_16 AC 445 ms
108,280 KB
testcase_17 AC 872 ms
152,780 KB
testcase_18 AC 1,623 ms
162,620 KB
testcase_19 AC 1,525 ms
162,976 KB
testcase_20 AC 1,466 ms
162,612 KB
testcase_21 AC 1,523 ms
163,432 KB
testcase_22 AC 1,471 ms
162,972 KB
testcase_23 AC 1,556 ms
163,284 KB
testcase_24 AC 1,541 ms
163,336 KB
testcase_25 AC 1,536 ms
162,936 KB
testcase_26 AC 1,578 ms
163,400 KB
testcase_27 AC 1,560 ms
163,700 KB
testcase_28 AC 1,606 ms
163,376 KB
testcase_29 AC 930 ms
163,492 KB
testcase_30 AC 934 ms
163,800 KB
testcase_31 AC 935 ms
163,676 KB
testcase_32 AC 933 ms
163,536 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# oj t -c "python3 main.py"
import sys,math
from collections import defaultdict,deque
from itertools import combinations,permutations,accumulate,product
from bisect import bisect_left,bisect_right
from heapq import heappop,heappush,heapify
#from more_itertools import distinct_permutations,distinct_combinations
#from sortedcontainers import SortedList,SortedSet
def input():return sys.stdin.readline().rstrip()
def ii(): return int(input())
def ms(): return map(int, input().split())
def li(): return list(map(int,input().split()))
inf = pow(10,18)
mod = 998244353
#/////////////////////////////////
N,Q = ms()
A = li()
class lazy_segtree(): # すべて 0-index
  def _update(self,k):self.data[k]=self.op(self.data[2*k],self.data[2*k+1])
  def _all_apply(self,k,f):
      self.data[k]=self.mapping(f,self.data[k])
      if (k<self.size):self.lz[k]=self.composition(f,self.lz[k])
  def _push(self,k):
      self._all_apply(2*k,self.lz[k])
      self._all_apply(2*k+1,self.lz[k])
      self.lz[k]=self.identity
  def __init__(self,V,OP,E,MAPPING,COMPOSITION,ID):
      self.n=len(V)
      self.log=(self.n-1).bit_length()
      self.size=1<<self.log
      self.data=[E for i in range(2*self.size)]
      self.lz=[ID for i in range(self.size)]
      self.e=E
      self.op=OP
      self.mapping=MAPPING
      self.composition=COMPOSITION
      self.identity=ID
      for i in range(self.n):self.data[self.size+i]=V[i]
      for i in range(self.size-1,0,-1):self._update(i)
  
  # 一点更新
  def set(self,p,x):
      assert 0<=p and p<self.n
      p+=self.size
      for i in range(self.log,0,-1):self._push(p>>i)
      self.data[p]=x
      for i in range(1,self.log+1):self._update(p>>i)
      
  # data[p] を取得する
  def get(self,p):
      assert 0<=p and p<self.n
      p+=self.size
      for i in range(self.log,0,-1):self._push(p>>i)
      return self.data[p]
    
  # 区間 [l,r) の演算結果を返す
  def prod(self,l,r):
      assert 0<=l and l<=r and r<=self.n
      if l==r:return self.e
      l+=self.size
      r+=self.size
      for i in range(self.log,0,-1):
          if (((l>>i)<<i)!=l):self._push(l>>i)
          if (((r>>i)<<i)!=r):self._push(r>>i)
      sml,smr=self.e,self.e
      while(l<r):
          if l&1:
              sml=self.op(sml,self.data[l])
              l+=1
          if r&1:
              r-=1
              smr=self.op(self.data[r],smr)
          l>>=1
          r>>=1
      return self.op(sml,smr)
  
  # 全区間の演算結果を返す
  def all_prod(self):return self.data[1]

  # 一点に対して操作する
  # あんまわからん
  def apply_point(self,p,f):
      assert 0<=p and p<self.n
      p+=self.size
      for i in range(self.log,0,-1):self._push(p>>i)
      self.data[p]=self.mapping(f,self.data[p])
      for i in range(1,self.log+1):self._update(p>>i)

  # 区間操作
  # f は mapping に与える引数の f
  def apply(self,l,r,f):
      assert 0<=l and l<=r and r<=self.n
      if l==r:return
      l+=self.size
      r+=self.size
      for i in range(self.log,0,-1):
          if (((l>>i)<<i)!=l):self._push(l>>i)
          if (((r>>i)<<i)!=r):self._push((r-1)>>i)
      l2,r2=l,r
      while(l<r):
          if (l&1):
              self._all_apply(l,f)
              l+=1
          if (r&1):
              r-=1
              self._all_apply(r,f)
          l>>=1
          r>>=1
      l,r=l2,r2
      for i in range(1,self.log+1):
          if (((l>>i)<<i)!=l):self._update(l>>i)
          if (((r>>i)<<i)!=r):self._update((r-1)>>i)
          
  # check(operate(data[l],data[l+1],...,data[r-1])) = True
  # を満たす最大の r を返す
  def max_right(self,l,check):
      assert 0<=l and l<=self.n
      assert check(self.e)
      if l==self.n:return self.n
      l+=self.size
      for i in range(self.log,0,-1):self._push(l>>i)
      sm=self.e
      while(1):
          while(l%2==0):l>>=1
          if not(check(self.op(sm,self.data[l]))):
              while(l<self.size):
                  self._push(l)
                  l=(2*l)
                  if (check(self.op(sm,self.data[l]))):
                      sm=self.op(sm,self.data[l])
                      l+=1
              return l-self.size
          sm=self.op(sm,self.data[l])
          l+=1
          if (l&-l)==l:break
      return self.n
  
  # check(operate(data[l],data[l+1],...,data[r-1])) = True
  # を満たす最小の l を返す
  def min_left(self,r,check):
      assert (0<=r and r<=self.n)
      assert check(self.e)
      if r==0:return 0
      r+=self.size
      for i in range(self.log,0,-1):self._push((r-1)>>i)
      sm=self.e
      while(1):
          r-=1
          while(r>1 and (r%2)):r>>=1
          if not(check(self.op(self.data[r],sm))):
              while(r<self.size):
                  self._push(r)
                  r=(2*r+1)
                  if g(self.op(self.data[r],sm)):
                      sm=self.op(self.data[r],sm)
                      r-=1
              return r+1-self.size
          sm=self.op(self.data[r],sm)
          if (r&-r)==r:break
      return 0

# data の単位元
e = 0
# lazy の単位元
# 区間更新なら lazy としてとりえない値にする
ide = 0

# 区間に対して行いたい演算
def operate(a,b):
  return a+b

# 遅延させていた操作をdataに伝搬させる関数
# f が遅延させた操作、x がdata
# ex. 区間加算なら f+x
def mapping(f,x):
  # 区間更新なら
  # if f==ide: return x
  return f+x

# 既に遅延させていた操作にさらに操作を追加する関数
# f が追加する操作、g がいままでの操作
def composition(f,g): 
  # 区間更新なら
  # if f==ide: return g
  return f+g

seg = lazy_segtree([0]*N,operate,e,mapping,composition,ide)

for _ in range(Q):
  l,r = ms()
  l -= 1
  seg.apply(l,r,1)
  
for i in range(N):
  if seg.get(i)%2==0:
    print(A[i],end=" ")
  else:
    print(1-A[i],end=" ")
0