結果
問題 | No.2080 Simple Nim Query |
ユーザー | 👑 p-adic |
提出日時 | 2024-08-18 19:45:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,503 ms / 3,000 ms |
コード長 | 5,965 bytes |
コンパイル時間 | 574 ms |
コンパイル使用メモリ | 82,156 KB |
実行使用メモリ | 171,332 KB |
最終ジャッジ日時 | 2024-08-18 19:45:51 |
合計ジャッジ時間 | 10,821 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 37 ms
54,636 KB |
testcase_01 | AC | 36 ms
55,640 KB |
testcase_02 | AC | 36 ms
55,804 KB |
testcase_03 | AC | 739 ms
80,144 KB |
testcase_04 | AC | 641 ms
77,300 KB |
testcase_05 | AC | 804 ms
171,332 KB |
testcase_06 | AC | 1,482 ms
151,996 KB |
testcase_07 | AC | 1,503 ms
151,720 KB |
testcase_08 | AC | 1,100 ms
152,024 KB |
testcase_09 | AC | 1,058 ms
152,132 KB |
testcase_10 | AC | 1,466 ms
153,548 KB |
ソースコード
def rec_str(a):return"".join(["[",", ".join(rec_str(x)for x in a),"]"])if isinstance(a,list)else str(a) class BIT: def __init__(self,x): if isinstance(x,int): self.N=x self.F=[0]*(x+1) else: self.N=len(x) self.F=[0]*(self.N+1) for j in R(1,self.N+1): i=j-1 self.F[j]=x[i] k=j-(j&-j) while i>k: self.F[j]+=self.F[i] i-=i&-i def copy(self): a=__class__([]) a.N=self.N a.F=self.F[:] return a def Add(self,i,u): i+=1 while i<=self.N: self.F[i]+=u i+=i&-i def Set(self,i,u):self.Add(i,u-self.Get(i)) def Get(self,i):return self.IntervalSum(i,i) def InitialSegmentSum(self,r): assert(r>-2) a=0 i=min(r+1,self.N) while i: a+=self.F[i] i-=i&-i return a def IntervalSum(self,l,r):return self.InitialSegmentSum(r)-self.InitialSegmentSum(l-1) def list(self):return[self.Get(i)for i in R(self.N)] def __str__(self):return rec_str(self.list()) def Search(self,u):#Computing minimum of j such that InitialSegmentSum(j)>=u or j==N j=s=n=0 p=1<<17 #131072 while p: k=j|p p>>=1 if k<=self.N: n+=self.F[k] if n<u:s,j=n,k else:n=s return j class NonNegativeLineSubset: def __init__(self,ubound): assert(-1<=ubound) self.ubound=ubound self.bit=BIT(ubound+1) def copy(self): a=__class__([]) a.ubound=self.ubound a.bit=self.bit.copy() return a def insert(self,i):assert(0<=i<=self.ubound);self.bit.Set(i,1) def erase(self,i):self.bit.Set(i,0) def count(self,i):return self.bit.Get(i)if 0<=i<=self.ubound else 0 def find(self,i):return self.count(i)>0 def InitialSegmentSize(self,i_final):return self.bit.InitialSegmentSum(i_final) def IntervalSize(self,i_start,i_final):returnself.bit.IntervalSum(i_start,i_final) def empty(self):return self.InitialSegmentSize(self.ubound)<1 def MaximumLeq(self,i):#Returning -1 if not exists num=self.InitialSegmentSize(i) def f(sum,j):return i<=j or num<=sum a=self.Search(f) return a if self.find(a)else -1 def MaximumLt(self,i):return self.MaximumLeq(i-1) def MinimumGeq(self,i):return self.MinimumGt(i-1) def MinimumGt(self,i):#Returning ubound+1 if not exists num=self.InitialSegmentSize(i) def f(sum,j):return i<j and num<sum return self.Search(f) def Maximum(self):return self.MaximumLeq(self.ubound) def Minimum(self):return self.MinimumGeq(0) def RightEndPointOf(self,i,b=False): if not b and not self.find(i):return i-1 comp=i-self.InitialSegmentSize(i) def f(sum,j):return i<=j and sum+comp<j return self.Search(f)-1 def LeftEndPointOf(self,i,b=False): if not b and not self.find(i):return i+1 comp=i-self.InitialSegmentSize(i) def f(sum,j):return i<=j or (self.find(j)and sum+comp==j) return self.Search(f) def ConnectedComponentOf(self,i,b=False): if not b:b=self.find(i) return[self.LeftEndPointOf(i,b),self.RightEndPointOf(i,b)] def GetConnectedComponent(self): a=[] l=self.Minimum() while l<=self.ubound: r=self.RightEndPointOf(l,True) a+=[[l,r]] l=self.MinimumGt(r) return a def __str__(self):return rec_str(self.GetConnectedComponent()) def ubound(self):return self.ubound #private: def Search(self,f):#Computing minimum of j satisfying f(InitialSegmentSum(j),j) or j==bit.N j=s=n=0 p=1<<17 #131072 while p: k=j|p p>>=1 if k<=self.bit.N: n+=self.bit.F[k] if f(n,k-1):n=s else:s,j=n,k return j class CompressedLineSubset: def __init__(self,X): self.sorted_list=sorted(set(X)) N=len(self.sorted_list) self.compressed_coordinate={self.sorted_list[i]:i for i in R(N)} self.nnls=NonNegativeLineSubset(N-1) def copy(self): a=__class__([]) a.sorted_list=self.sorted_list[:] a.compressed_coordinate=self.copy() a.nnls=self.nnls.copy() return a def insert(self,i):self.nnls.insert(self.compressed_coordinate[i]) def erase(self,i):self.nnls.erase(self.compressed_coordinate[i]) def count(self,i):return self.nnls.count(self.compressed_coordinate[i])if i in self.compressed_coordinate else 0 def find(self,i):return self.count(i)>0 def InitialSegmentSize(self,i_final):return self.nnls.InitialSegmentSize(self.compressed_coordinate[i_final]) def IntervalSize(self,i_start,i_final):return self.nnls.IntervalSum(self.compressed_coordinate[i_start],self.compressed_coordinate[i_final]) def empty(self):return self.InitialSegmentSize(self.nnls.bit.N-1)<1 def MaximumLeq(self,i): t=self.nnls.MaximumLeq(self.compressed_coordinate[i]) return self.sorted_list[t]if t>=0 else None def MaximumLt(self,i): t=self.nnls.MaximumLt(self.compressed_coordinate[i]) return self.sorted_list[t]if t>=0 else None def MinimumGeq(self,i): t=self.nnls.MinimumGeq(self.compressed_coordinate[i]) return self.sorted_list[t]if t<self.nnls.bit.N else None def MinimumGt(self,i): t=self.nnls.MinimumGt(self.compressed_coordinate[i]) return self.sorted_list[t]if t<self.nnls.bit.N else None def Maximum(self):return self.MaximumLeq(self.sorted_list[-1]) def Minimum(self):return self.MinimumGeq(self.sorted_list[0]) def RightEndPointOf(self,i,b=False): j=self.compressed_coordinate[i] t=self.nnls.RightEndPointOf(j,b) return self.sorted_list[t]if j<=t else i-1 def LeftEndPointOf(self,i,b=False): j=self.compressed_coordinate[i] t=self.nnls.LeftEndPointOf(j,b) return self.sorted_list[t]if t<=j else i+1 def ConnectedComponentOf(self,i,b=False): if not b:b=self.find(i) return[self.LeftEndPointOf(i,b),self.RightEndPointOf(i,b)] def GetConnectedComponent(self): a=[] l=self.Minimum() while l is not None: r=self.RightEndPointOf(l,True) a+=[[l,r]] l=self.MinimumGt(r) return a def __str__(self):return rec_str(self.GetConnectedComponent()) R=range J=lambda:map(int,input().split()) N,Q=J() A=list(J()) S=CompressedLineSubset(list(R(N))) for i in R(N): if A[i]==1:S.insert(i) for _ in R(Q): T,X,Y=J() if T==1: X-=1 S.erase(X) if Y==1:S.insert(X) else: X-=1;Y-=1 l,r=S.ConnectedComponentOf(Y) print("SF"[r<Y or ((Y-max(X,l))&1)==(X<l)])