結果
問題 | No.2421 entersys? |
ユーザー |
|
提出日時 | 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 |
ソースコード
class BIT:def __init__(self, n):self.size = nself.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 = 0while i>0:s += self.tree[i]i -= i & -ireturn s# 0 index を 1 index に変更 転倒数を求めるなら1を足していくdef add(self, i, x):i += 1while i <= self.size:self.tree[i] += xi += i & -i# 総和がx以上になる位置のindex をbinary searchdef bsearch(self,x):le = 0ri = 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 += riri >>= 1return le+1n = 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)