結果
問題 | No.2421 entersys? |
ユーザー | miya145592 |
提出日時 | 2023-08-12 14:34:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,422 ms / 3,000 ms |
コード長 | 2,784 bytes |
コンパイル時間 | 337 ms |
コンパイル使用メモリ | 82,156 KB |
実行使用メモリ | 264,772 KB |
最終ジャッジ日時 | 2024-04-30 06:30:40 |
合計ジャッジ時間 | 20,505 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 32 ms
53,464 KB |
testcase_01 | AC | 46 ms
64,468 KB |
testcase_02 | AC | 60 ms
73,700 KB |
testcase_03 | AC | 36 ms
55,512 KB |
testcase_04 | AC | 47 ms
64,564 KB |
testcase_05 | AC | 57 ms
70,368 KB |
testcase_06 | AC | 60 ms
69,176 KB |
testcase_07 | AC | 63 ms
69,708 KB |
testcase_08 | AC | 65 ms
71,864 KB |
testcase_09 | AC | 88 ms
77,076 KB |
testcase_10 | AC | 60 ms
67,588 KB |
testcase_11 | AC | 864 ms
227,240 KB |
testcase_12 | AC | 886 ms
227,808 KB |
testcase_13 | AC | 872 ms
227,836 KB |
testcase_14 | AC | 866 ms
227,784 KB |
testcase_15 | AC | 841 ms
227,444 KB |
testcase_16 | AC | 881 ms
220,200 KB |
testcase_17 | AC | 869 ms
215,920 KB |
testcase_18 | AC | 838 ms
216,444 KB |
testcase_19 | AC | 866 ms
216,192 KB |
testcase_20 | AC | 867 ms
215,308 KB |
testcase_21 | AC | 724 ms
204,184 KB |
testcase_22 | AC | 709 ms
222,684 KB |
testcase_23 | AC | 1,007 ms
264,184 KB |
testcase_24 | AC | 990 ms
264,624 KB |
testcase_25 | AC | 985 ms
264,772 KB |
testcase_26 | AC | 1,392 ms
224,272 KB |
testcase_27 | AC | 1,414 ms
224,132 KB |
testcase_28 | AC | 1,422 ms
227,840 KB |
ソースコード
# https://nagiss.hateblo.jp/entry/2019/07/01/185421 class Bit: def __init__(self, n): self.size = n self.tree = [0]*(n+1) def __iter__(self): psum = 0 for i in range(self.size): csum = self.sum(i+1) yield csum - psum psum = csum raise StopIteration() def __str__(self): # O(nlogn) return str(list(self)) def sum(self, i): # [0, i) の要素の総和を返す if not (0 <= i <= self.size): raise ValueError("error!") s = 0 while i>0: s += self.tree[i] i -= i & -i return s def add(self, i, x): if not (0 <= i < self.size): raise ValueError("error!") i += 1 while i <= self.size: self.tree[i] += x i += i & -i def __getitem__(self, key): if not (0 <= key < self.size): raise IndexError("error!") return self.sum(key+1) - self.sum(key) def __setitem__(self, key, value): # 足し算と引き算にはaddを使うべき if not (0 <= key < self.size): raise IndexError("error!") self.add(key, value - self[key]) import bisect N = int(input()) XLR = [input().split() for _ in range(N)] T = set() X = dict() for x, l, r in XLR: l = int(l) r = int(r) T.add(l) T.add(r) if x not in X: X[x] = [] bisect.insort_left(X[x], l) bisect.insort_left(X[x], r) Q = int(input()) query = [input().split() for _ in range(Q)] for q in query: tp = q[0] if tp=="1": x = q[1] t = int(q[2]) T.add(t) elif tp=="2": t = int(q[1]) T.add(t) else: x = q[1] l = int(q[2]) r = int(q[3]) T.add(l) T.add(r) T = list(T) T.sort() Z = dict() for i, t in enumerate(T): Z[t] = i BIT = Bit(len(T)+1) for x, l, r in XLR: l=int(l) r=int(r) BIT.add(Z[l], 1) BIT.add(Z[r]+1, -1) for q in query: tp = q[0] if tp=="1": x = q[1] t = int(q[2]) if x not in X: print("No") else: pos = bisect.bisect_left(X[x], t) if pos==len(X[x]): print("No") else: if pos%2==0: if X[x][pos]==t: print("Yes") else: print("No") else: print("Yes") elif tp=="2": t = int(q[1]) ans = BIT.sum(Z[t]+1) print(ans) else: x = q[1] l = int(q[2]) r = int(q[3]) BIT.add(Z[l], 1) BIT.add(Z[r]+1, -1) if x not in X: X[x] = [] bisect.insort_left(X[x], l) bisect.insort_left(X[x], r)