結果
問題 | No.2421 entersys? |
ユーザー | gr1msl3y |
提出日時 | 2023-08-17 18:36:27 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,306 bytes |
コンパイル時間 | 320 ms |
コンパイル使用メモリ | 82,572 KB |
実行使用メモリ | 221,084 KB |
最終ジャッジ日時 | 2024-11-26 17:43:18 |
合計ジャッジ時間 | 22,813 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
53,316 KB |
testcase_01 | AC | 58 ms
65,896 KB |
testcase_02 | WA | - |
testcase_03 | AC | 50 ms
62,040 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | AC | 68 ms
69,520 KB |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | AC | 931 ms
187,652 KB |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
ソースコード
from bisect import bisect_leftclass Bit:def __init__(self, n):self.size = nself.tree = [0] * (n + 1)def sum(self, i):i += 1s = 0while i > 0:s += self.tree[i]i -= i & -ireturn sdef sumrange(self, i, j):si = self.sum(i - 1)sj = self.sum(j)return sj - sidef add(self, i, x):i += 1while i <= self.size:self.tree[i] += xi += i & -idef lower_bound(self, w):if w <= 0:return 0x = 0r = 1 << (self.size).bit_length()while r > 0:if x+r < self.size and self.tree[x+r] < w:w -= self.tree[x+r]x += rr = r >> 1return xN = int(input())data = {}S = {-1, 2*10**9}T = {}for _ in range(N):s, l, r = input().split()l = int(l)r = int(r)+1if s in data:data[s].append([l, r])T[s].add(l)T[s].add(r)else:data[s] = [[l, r]]T[s] = {l, r}S.add(l)S.add(r)Q = int(input())qq = [list(input().split()) for _ in range(Q)]query = []for q in qq:if q[0] == '1':t = int(q[2])query.append([1, q[1], t])S.add(t)elif q[0] == '2':t = int(q[1])query.append([2, t])S.add(t)else:x, l, r = q[1], int(q[2]), int(q[3])query.append([3, x, l, r])S.add(l)S.add(r)if x in T:T[x].add(l)T[x].add(r)else:T[x] = {l, r}S = sorted(list(S))state = Bit(len(S)+1)for k in data:data[k].sort()for l, r in data[k]:state.add(bisect_left(S, l), 1)state.add(bisect_left(S, r), -1)for k in T:T[k] = sorted(list(T[k]))ans = []for q in query:if q[0] == 1:x, t = q[1], q[2]+1if x not in T:ans.append('No')else:ans.append('Yes' if bisect_left(T[x], t) else 'No')elif q[0] == 2:t = q[1]ans.append(state.sum(bisect_left(S, t)))else:l, r = q[2:]indl = bisect_left(S, l)indr = bisect_left(S, r)state.add(indl, 1)state.add(indr, -1)print(*ans, sep='\n')