結果

問題 No.2421 entersys?
ユーザー lloyz
提出日時 2024-01-17 07:23:21
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,593 ms / 3,000 ms
コード長 6,721 bytes
コンパイル時間 493 ms
コンパイル使用メモリ 82,424 KB
実行使用メモリ 270,824 KB
最終ジャッジ日時 2024-09-28 03:09:54
合計ジャッジ時間 28,341 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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

class Fenwick_Tree:
def __init__(self, n):
self.n = n
self.data = [0] * n
def add(self, p, x):
p += 1
while p <= self.n:
self.data[p - 1] += x
p += p & -p
def sum(self, l, r):
'''[l, r)(lr-1)'''
return self._sum(r) - self._sum(l)
def _sum(self, r):
'''[0, r)(0r-1)'''
s = 0
while r > 0:
s += self.data[r - 1]
r -= r & -r
return s
# 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
def compression(lst):
sort_lst = sorted(set(lst))
compression_lst = [None for _ in range(len(lst))]
ele2ind_dict = dict()
for i, ele in enumerate(lst):
compression_lst[i] = bisect_left(sort_lst, ele)
ele2ind_dict[ele] = compression_lst[i]
return sort_lst, compression_lst, ele2ind_dict
import sys
def input():
return sys.stdin.readline().rstrip()
n = int(input())
T = []
X = []
for _ in range(n):
x, l, r = input().split()
l = int(l)
r = int(r)
T.append(l)
T.append(r)
X.append((x, l, r))
q = int(input())
Q = []
for _ in range(q):
QQ = list(input().split())
Q.append(QQ)
if QQ[0] == '1':
T.append(int(QQ[2]))
elif QQ[0] == '2':
T.append(int(QQ[1]))
else:
T.append(int(QQ[2]))
T.append(int(QQ[3]))
_, _, Tdict = compression(T)
m = len(Tdict)
tree = Fenwick_Tree(m + 5)
L = dict()
R = dict()
for i in range(n):
x, l, r = X[i]
if x not in L:
L[x] = SortedMultiset()
R[x] = SortedMultiset()
L[x].add(Tdict[l])
tree.add(Tdict[l], 1)
R[x].add(Tdict[r])
tree.add(Tdict[r] + 1, -1)
for i in range(q):
QQ = Q[i]
if QQ[0] == '1':
x, t = QQ[1:]
t = int(t)
if x not in L:
print("No")
continue
tidx = Tdict[t]
idx = bisect_right(L[x], tidx) - 1
if idx == -1:
print("No")
continue
r = R[x][idx]
if tidx <= r:
print("Yes")
else:
print("No")
elif QQ[0] == '2':
t = QQ[1]
t = int(t)
tidx = Tdict[t]
print(tree._sum(tidx + 1))
else:
x, l, r = QQ[1:]
l = int(l)
r = int(r)
if x not in L:
L[x] = SortedMultiset()
R[x] = SortedMultiset()
L[x].add(Tdict[l])
tree.add(Tdict[l], 1)
R[x].add(Tdict[r])
tree.add(Tdict[r] + 1, -1)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0