結果

問題 No.2421 entersys?
ユーザー aaaaaaaaaa2230
提出日時 2023-08-12 14:29:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,659 ms / 3,000 ms
コード長 3,070 bytes
コンパイル時間 252 ms
コンパイル使用メモリ 82,224 KB
実行使用メモリ 316,588 KB
最終ジャッジ日時 2024-11-19 19:46:58
合計ジャッジ時間 25,983 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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

class BIT:
def __init__(self, n):
self.size = n
self.tree = [0]*(n+1)
def build(self, list):
self.tree[1:] = list.copy()
for i in range(self.size+1):
j = i + (i & (-i))
if j < self.size+1:
self.tree[j] += self.tree[i]
def sum(self, i):
# [0, i)
s = 0
while i>0:
s += self.tree[i]
i -= i & -i
return s
# 0 index 1 index 1
def add(self, i, x):
i += 1
while i <= self.size:
self.tree[i] += x
i += i & -i
# xindex binary search
def bsearch(self,x):
le = 0
ri = 1<<(self.size.bit_length()-1)
while ri > 0:
if le+ri <= self.size and self.tree[le+ri]<x:
x -= self.tree[le+ri]
le += ri
ri >>= 1
return le+1
n = int(input())
member = {}
alls = set()
XLR = []
for i in range(n):
x,l,r = input().split()
l,r = int(l),int(r)
if x not in member:
member[x] = set()
member[x].add(l)
member[x].add(r+1)
alls.add(l)
alls.add(r+1)
XLR.append([x,l,r])
q = int(input())
Q = []
for _ in range(q):
l = input().split()
if l[0] == "1":
if l[1] not in member:
member[l[1]] = set()
l[0] = int(l[0])
l[2] = int(l[2])
member[l[1]].add(l[2])
Q.append(l)
elif l[0] == "2":
l[0] = int(l[0])
l[1] = int(l[1])
alls.add(l[1])
Q.append(l)
else:
if l[1] not in member:
member[l[1]] = set()
l[0] = int(l[0])
l[2] = int(l[2])
l[3] = int(l[3])
member[l[1]].add(l[2])
member[l[1]].add(l[3]+1)
alls.add(l[2])
alls.add(l[3]+1)
Q.append(l)
keys = sorted(member.keys())
member_dic = {x:i for i,x in enumerate(keys)}
bits = [BIT(len(member[key])) for key in keys]
compress = []
for key in keys:
comp_keys = {x:i for i,x in enumerate(sorted(member[key]))}
compress.append(comp_keys)
all_coms = {x:i for i,x in enumerate(sorted(alls))}
all_bit = BIT(len(all_coms))
for x,l,r in XLR:
num = member_dic[x]
bits[num].add(compress[num][l],1)
bits[num].add(compress[num][r+1],-1)
all_bit.add(all_coms[l],1)
all_bit.add(all_coms[r+1],-1)
for q in Q:
# print("query",q)
if q[0] == 1:
# print("A")
num = member_dic[q[1]]
pos = compress[num][q[2]]
if bits[num].sum(pos+1):
print("Yes")
else:
print("No")
elif q[0] == 2:
# print("B")
pos = all_coms[q[1]]
print(all_bit.sum(pos+1))
else:
# print(q)
# print("C")
num = member_dic[q[1]]
l,r = q[2:]
all_bit.add(all_coms[l],1)
all_bit.add(all_coms[r+1],-1)
bits[num].add(compress[num][l],1)
bits[num].add(compress[num][r+1],-1)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0