結果

問題 No.2421 entersys?
ユーザー kemuniku
提出日時 2023-08-12 14:57:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,861 ms / 3,000 ms
コード長 8,285 bytes
コンパイル時間 373 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 263,280 KB
最終ジャッジ日時 2024-11-19 22:25:39
合計ジャッジ時間 32,515 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import math
from bisect import bisect_left, bisect_right, insort
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
T = TypeVar('T')
class SortedMultiset(Generic[T]):
BUCKET_RATIO = 50
REBUILD_RATIO = 170
def _build(self, a=None) -> None:
"Evenly divide `a` into buckets."
if a is None: a = list(self)
size = 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)
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 j
def __reversed__(self) -> Iterator[T]:
for i in reversed(self.a):
for j in reversed(i): yield j
def __len__(self) -> int:
return self.size
def __repr__(self) -> str:
return "SortedMultiset" + str(self.a)
def __str__(self) -> str:
s = str(list(self))
return "{" + s[1 : len(s) - 1] + "}"
def _find_bucket(self, x: T) -> List[T]:
"Find the bucket which should contain x. self must not be empty."
for a in self.a:
if x <= a[-1]: return a
return a
def __contains__(self, x: T) -> bool:
if self.size == 0: return False
a = self._find_bucket(x)
i = bisect_left(a, x)
return i != len(a) and a[i] == x
def 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 = 1
return
a = self._find_bucket(x)
insort(a, x)
self.size += 1
if len(a) > len(self.a) * self.REBUILD_RATIO:
self._build()
def discard(self, x: T) -> bool:
"Remove an element and return True if removed. / O(√N)"
if self.size == 0: return False
a = self._find_bucket(x)
i = bisect_left(a, x)
if i == len(a) or a[i] != x: return False
a.pop(i)
self.size -= 1
if len(a) == 0: self._build()
return True
def lt(self, x: T) -> Union[T, None]:
"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) -> Union[T, None]:
"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) -> Union[T, None]:
"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) -> Union[T, None]:
"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, x: int) -> T:
"Return the x-th element, or IndexError if it doesn't exist."
if x < 0: x += self.size
if x < 0: raise IndexError
for a in self.a:
if x < len(a): return a[x]
x -= len(a)
raise IndexError
def index(self, x: T) -> int:
"Count the number of elements < x."
ans = 0
for a in self.a:
if a[-1] >= x:
return ans + bisect_left(a, x)
ans += len(a)
return ans
def index_right(self, x: T) -> int:
"Count the number of elements <= x."
ans = 0
for a in self.a:
if a[-1] > x:
return ans + bisect_right(a, x)
ans += len(a)
return ans
class SegmentTree:
def __init__(self, v,marge,default):
self.default = default
self.marge = marge
self.lastnode = 1
self.h = 1
while self.lastnode < len(v):
self.lastnode*=2
self.h += 1
#1-indexed
self.array = [self.default] *(2*self.lastnode)
self.lazy = [0] *(2*self.lastnode)
for i in range(len(v)):
self.array[self.lastnode+i] = v[i]
for i in range(self.lastnode-1,-1,-1):
self.array[i] = self.marge(self.array[2*i],self.array[2*i+1])
def propagate(self,i):
if self.lazy[i] != 0:
v = self.lazy[i] #
if i < self.lastnode:
self.lazy[i] = 0
self.lazy[2*i]+= v
self.lazy[2*i+1] += v
self.array[2*i] += v
self.array[2*i+1] += v
self.lazy[i] = 0
def eval(self,L,R):
L+=self.lastnode
R+=self.lastnode
L0 = L // (L & -L) # L 2
R0 = R // (R & -R) # R 2
H = L0.bit_length() - 1
for n in range(H, -1, -1):
self.propagate(L0>>n)
H = R0.bit_length() - 1
for n in range(H, -1, -1):
self.propagate(R0>>n)
def recalc(self,L,R):
L+=self.lastnode
R+=self.lastnode
L0 = L // (L & -L) # L 2
R0 = R // (R & -R) # R 2
while L0 > 1:
L0 >>= 1
self.array[L0] = self.marge(self.array[2*L0],self.array[2*L0+1])
while R0 > 1:
R0 >>= 1
self.array[R0] = self.marge(self.array[2*R0],self.array[2*R0+1])
def add(self,q_left , q_right,val):
self.eval(q_left , q_right)
L,R = q_left, q_right
q_left += self.lastnode
q_right += self.lastnode
while q_left < q_right:
if q_left&1:
self.array[q_left] += val
self.lazy[q_left] += val
q_left += 1
if q_right&1:
q_right -= 1
self.array[q_right] +=val
self.lazy[q_right] += val
q_left >>= 1
q_right>>= 1
self.recalc(L,R)
def query(self,q_left,q_right):
self.eval(q_left , q_right)
q_left += self.lastnode
q_right += self.lastnode
lres,rres = self.default,self.default
while q_left < q_right:
if q_left&1:
lres = self.marge(lres,self.array[q_left])
q_left += 1
if q_right&1:
q_right -= 1
rres = self.marge(self.array[q_right],rres)
q_left >>= 1
q_right>>= 1
return self.marge(lres,rres)
from collections import defaultdict
N = int(input())
enter = defaultdict(SortedMultiset)
info = []
times = set()
for i in range(N):
X,L,R = input().split()
L = int(L)
R = int(R)
info.append((X,L,R))
times.add(L)
times.add(R)
Q = int(input())
querys = []
for i in range(Q):
q,*arg = input().split()
q = int(q)
querys.append((q,arg))
if q == 1:
times.add(int(arg[1]))
elif q == 2:
times.add(int(arg[0]))
else:
times.add(int(arg[1]))
times.add(int(arg[2]))
compttmp = sorted(list(times))
compt = {compttmp[i]:i for i in range(len(compttmp))}
st = SegmentTree([0]*len(compt),lambda x,y:x+y,0)
for X,L,R in info:
enter[X].add((L,R))
st.add(compt[L],compt[R]+1,1)
for q,arg in querys:
if q == 1:
x,t = arg
t = int(t)
z = enter[x].lt((t,10**18))
if z is None:
print("No")
else:
l,r = z
if l <= t <= r:
print("Yes")
else:
print("No")
elif q == 2:
t = int(arg[0])
print(st.query(compt[t],compt[t]+1))
else:
x,l,r = arg
l = int(l)
r = int(r)
enter[x].add((l,r))
st.add(compt[l],compt[r]+1,1)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0