結果
問題 | No.2421 entersys? |
ユーザー | aaaaaaaaaa2230 |
提出日時 | 2023-08-12 14:29:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,631 ms / 3,000 ms |
コード長 | 3,070 bytes |
コンパイル時間 | 336 ms |
コンパイル使用メモリ | 82,252 KB |
実行使用メモリ | 316,192 KB |
最終ジャッジ日時 | 2024-04-30 06:17:43 |
合計ジャッジ時間 | 24,903 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 35 ms
53,268 KB |
testcase_01 | AC | 49 ms
65,224 KB |
testcase_02 | AC | 77 ms
77,648 KB |
testcase_03 | AC | 39 ms
61,176 KB |
testcase_04 | AC | 46 ms
64,876 KB |
testcase_05 | AC | 61 ms
72,704 KB |
testcase_06 | AC | 61 ms
73,140 KB |
testcase_07 | AC | 61 ms
72,672 KB |
testcase_08 | AC | 73 ms
77,312 KB |
testcase_09 | AC | 94 ms
77,964 KB |
testcase_10 | AC | 60 ms
71,080 KB |
testcase_11 | AC | 1,170 ms
261,768 KB |
testcase_12 | AC | 1,234 ms
261,804 KB |
testcase_13 | AC | 1,212 ms
262,128 KB |
testcase_14 | AC | 1,195 ms
262,444 KB |
testcase_15 | AC | 1,167 ms
262,380 KB |
testcase_16 | AC | 1,314 ms
263,272 KB |
testcase_17 | AC | 1,316 ms
260,668 KB |
testcase_18 | AC | 1,328 ms
263,260 KB |
testcase_19 | AC | 1,347 ms
263,632 KB |
testcase_20 | AC | 1,330 ms
261,148 KB |
testcase_21 | AC | 1,199 ms
244,328 KB |
testcase_22 | AC | 1,031 ms
253,124 KB |
testcase_23 | AC | 1,619 ms
316,020 KB |
testcase_24 | AC | 1,622 ms
316,136 KB |
testcase_25 | AC | 1,631 ms
316,192 KB |
testcase_26 | AC | 831 ms
248,488 KB |
testcase_27 | AC | 826 ms
250,716 KB |
testcase_28 | AC | 851 ms
256,328 KB |
ソースコード
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 # 総和がx以上になる位置のindex を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)