結果
問題 | No.2421 entersys? |
ユーザー |
![]() |
提出日時 | 2023-08-12 15:14:42 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,484 ms / 3,000 ms |
コード長 | 8,115 bytes |
コンパイル時間 | 384 ms |
コンパイル使用メモリ | 82,352 KB |
実行使用メモリ | 233,132 KB |
最終ジャッジ日時 | 2024-11-20 00:53:50 |
合計ジャッジ時間 | 38,660 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#遅延セグメント木https://qiita.com/ether2420/items/7b67b2b35ad5f441d686defdef segfunc(x,y):return x+yclass LazySegTree_RAQ:def __init__(self,init_val,segfunc,ide_ele):n = len(init_val)self.segfunc = segfuncself.ide_ele = ide_eleself.num = 1<<(n-1).bit_length()self.tree = [ide_ele]*2*self.numself.lazy = [0]*2*self.numfor i in range(n):self.tree[self.num+i] = init_val[i]for i in range(self.num-1,0,-1):self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1])def gindex(self,l,r):l += self.numr += self.numlm = l>>(l&-l).bit_length()rm = r>>(r&-r).bit_length()while r>l:if l<=lm:yield lif r<=rm:yield rr >>= 1l >>= 1while l:yield ll >>= 1def propagates(self,*ids):for i in reversed(ids):v = self.lazy[i]if v==0:continueself.lazy[i] = 0self.lazy[2*i] += vself.lazy[2*i+1] += vself.tree[2*i] += vself.tree[2*i+1] += vdef add(self,l,r,x):ids = self.gindex(l,r)l += self.numr += self.numwhile l<r:if l&1:self.lazy[l] += xself.tree[l] += xl += 1if r&1:self.lazy[r-1] += xself.tree[r-1] += xr >>= 1l >>= 1for i in ids:self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1]) + self.lazy[i]def query(self,l,r):self.propagates(*self.gindex(l,r))res = self.ide_elel += self.numr += self.numwhile l<r:if l&1:res = self.segfunc(res,self.tree[l])l += 1if r&1:res = self.segfunc(res,self.tree[r-1])l >>= 1r >>= 1return res# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.pyimport mathfrom bisect import bisect_left, bisect_rightfrom typing import Generic, Iterable, Iterator, List, Tuple, TypeVar, OptionalT = TypeVar('T')class SortedMultiset(Generic[T]):BUCKET_RATIO = 50REBUILD_RATIO = 170def _build(self, a: Optional[List[T]] = None) -> None:if a is None: a = list(self)size = len(a)bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))self.a = [a[size * i // bucket_size : size * (i + 1) // bucket_size] for i in range(bucket_size)]def __init__(self, a: Iterable[T] = []) -> None:#Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)a = list(a)self.size = len(a)if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):a = sorted(a)self._build(a)def __iter__(self) -> Iterator[T]:for i in self.a:for j in i: yield jdef __reversed__(self) -> Iterator[T]:for i in reversed(self.a):for j in reversed(i): yield jdef __eq__(self, other) -> bool:return list(self) == list(other)def __len__(self) -> int:return self.sizedef __repr__(self) -> str:return str(self.a)def __str__(self) -> str:s = str(list(self))return sdef _position(self, x: T) -> Tuple[List[T], int]:#Find the bucket and position which x should be inserted. self must not be empty.for a in self.a:if x <= a[-1]: breakreturn (a, bisect_left(a, x))def __contains__(self, x: T) -> bool:if self.size == 0: return Falsea, i = self._position(x)return i != len(a) and a[i] == xdef count(self, x: T) -> int:#Count the number of x.return self.index_right(x) - self.index(x)def add(self, x: T) -> None:#Add an element. / O(√N)if self.size == 0:self.a = [[x]]self.size = 1returna, i = self._position(x)a.insert(i, x)self.size += 1if len(a) > len(self.a) * self.REBUILD_RATIO:self._build()def _pop(self, a: List[T], i: int) -> T:ans = a.pop(i)self.size -= 1if not a: self._build()return ansdef discard(self, x: T) -> bool:#Remove an element and return True if removed. / O(√N)if self.size == 0: return Falsea, i = self._position(x)if i == len(a) or a[i] != x: return Falseself._pop(a, i)return Truedef lt(self, x: T) -> Optional[T]:#Find the largest element < x, or None if it doesn't exist.for a in reversed(self.a):if a[0] < x:return a[bisect_left(a, x) - 1]def le(self, x: T) -> Optional[T]:#Find the largest element <= x, or None if it doesn't exist.for a in reversed(self.a):if a[0] <= x:return a[bisect_right(a, x) - 1]def gt(self, x: T) -> Optional[T]:#Find the smallest element > x, or None if it doesn't exist.for a in self.a:if a[-1] > x:return a[bisect_right(a, x)]def ge(self, x: T) -> Optional[T]:#Find the smallest element >= x, or None if it doesn't exist.for a in self.a:if a[-1] >= x:return a[bisect_left(a, x)]def __getitem__(self, i: int) -> T:#Return the i-th element.if i < 0:for a in reversed(self.a):i += len(a)if i >= 0: return a[i]else:for a in self.a:if i < len(a): return a[i]i -= len(a)raise IndexErrordef pop(self, i: int = -1) -> T:#Pop and return the i-th element.if i < 0:for a in reversed(self.a):i += len(a)if i >= 0: return self._pop(a, i)else:for a in self.a:if i < len(a): return self._pop(a, i)i -= len(a)raise IndexErrordef index(self, x: T) -> int:#Count the number of elements < x.ans = 0for a in self.a:if a[-1] >= x:return ans + bisect_left(a, x)ans += len(a)return ansdef index_right(self, x: T) -> int:#Count the number of elements <= x.ans = 0for a in self.a:if a[-1] > x:return ans + bisect_right(a, x)ans += len(a)return ansimport sysfrom collections import defaultdictimport bisectinput=sys.stdin.readlinedat1=[]N=int(input())zaatu=set()for i in range(N):X,L,R=map(str,input().split())L=int(L)R=int(R)zaatu.add(L)zaatu.add(R)dat1.append([X,L,R])Q=int(input())q=[]for _ in range(Q):qi=list(map(str,input().split()))q.append(qi)if qi[0]=='3':zaatu.add(int(qi[2]))zaatu.add(int(qi[3]))elif qi[0]=='2':zaatu.add(int(qi[1]))zaatu=sorted(list(zaatu))dic=defaultdict(SortedMultiset)st=LazySegTree_RAQ([0 for i in range(len(zaatu))],max,0)for i in range(N):X,L,R=dat1[i]dic[X].add(L)dic[X].add(R+1)left=bisect.bisect_left(zaatu,L)right=bisect.bisect_left(zaatu,R)st.add(left,right+1,1)for qi in q:if qi[0]=='1':d,x,t=qit=int(t)l=dic[x].index_right(t)if l%2==1:print('Yes')else:print('No')elif qi[0]=='2':qi[1]=int(qi[1])bi=bisect.bisect_left(zaatu,qi[1])print(st.query(bi,bi+1))elif qi[0]=='3':d,X,L,R=qiL=int(L)R=int(R)dic[X].add(L)dic[X].add(R+1)left=bisect.bisect_left(zaatu,L)right=bisect.bisect_left(zaatu,R)st.add(left,right+1,1)