結果
問題 | No.2421 entersys? |
ユーザー |
![]() |
提出日時 | 2023-08-12 14:18:32 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,028 ms / 3,000 ms |
コード長 | 2,816 bytes |
コンパイル時間 | 457 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 244,548 KB |
最終ジャッジ日時 | 2024-11-19 18:30:15 |
合計ジャッジ時間 | 18,440 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
import sys# sys.setrecursionlimit(200005)# sys.set_int_max_str_digits(1000005)int1 = lambda x: int(x)-1pDB = lambda *x: print(*x, end="\n", file=sys.stderr)p2D = lambda x: print(*x, sep="\n", end="\n\n", file=sys.stderr)def II(): return int(sys.stdin.readline())def LI(): return list(map(int, sys.stdin.readline().split()))def LLI(rows_number): return [LI() for _ in range(rows_number)]def LI1(): return list(map(int1, sys.stdin.readline().split()))def LLI1(rows_number): return [LI1() for _ in range(rows_number)]def SI(): return sys.stdin.readline().rstrip()# dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]inf = -1-(-1 << 63)# md = 10**9+7md = 998244353class BitSum:def __init__(self, n):self._n = n+1self._table = [0]*self._nself._origin = [0]*ndef __getitem__(self, item):return self._origin[item]def add(self, i, x):self._origin[i] += xi += 1while i < self._n:self._table[i] += xi += i & -idef sum(self, i):i += 1res = 0while i > 0:res += self._table[i]i -= i & -ireturn resdef sumlr(self, l, r):if l >= r: return 0if l == 0: return self.sum(r-1)return self.sum(r-1)-self.sum(l-1)# return "min(i) of sum(i)>=x" or "N"def bisect(self, x):idx = 0d = 1 << (self._n-1).bit_length()-1while d:if idx+d < self._n and self._table[idx+d] < x:x -= self._table[idx+d]idx |= dd >>= 1return idxfrom bisect import *from collections import defaultdictn=II()lr=defaultdict(list)dec=set()for _ in range(n):x,l,r=SI().split()l,r=int(l),int(r)lr[x].append((l,r+1))dec.add(l)dec.add(r+1)q=II()task=[]for _ in range(q):qt,*xt=SI().split()qt=int(qt)if qt==1:dec.add(int(xt[1]))if qt==2:dec.add(int(xt[0]))if qt==3:x,l,r=xtdec.add(int(l))dec.add(int(r)+1)task.append((qt,xt))enc={a:i for i,a in enumerate(sorted(dec))}bit=BitSum(len(dec)+5)for x in lr:for l,r in lr[x]:l=enc[l]r=enc[r]bit.add(l,1)bit.add(r,-1)lr[x].sort(key=lambda x:x[0])for qt,xt in task:if qt==1:x,t=xtt=int(t)i=bisect(lr[x],(t,inf))if i and t<lr[x][i-1][1]:print("Yes")else:print("No")elif qt==2:t=int(xt[0])t=enc[t]print(bit.sum(t))else:x,l,r=xtl,r=int(l),int(r)+1insort(lr[x],(l,r))l,r=enc[l],enc[r]bit.add(l,1)bit.add(r,-1)