結果

問題 No.2421 entersys?
コンテスト
ユーザー kemuniku
提出日時 2023-08-12 14:57:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,861 ms / 3,000 ms
コード長 8,285 bytes
コンパイル時間 373 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 263,280 KB
最終ジャッジ日時 2024-11-19 22:25:39
合計ジャッジ時間 32,515 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

# https://github.com/tatyam-prime/SortedSet/blob/main/SortedMultiset.py
import math
from bisect import bisect_left, bisect_right, insort
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
T = TypeVar('T')

class SortedMultiset(Generic[T]):
    BUCKET_RATIO = 50
    REBUILD_RATIO = 170

    def _build(self, a=None) -> None:
        "Evenly divide `a` into buckets."
        if a is None: a = list(self)
        size = self.size = len(a)
        bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))
        self.a = [a[size * i // bucket_size : size * (i + 1) // bucket_size] for i in range(bucket_size)]
    
    def __init__(self, a: Iterable[T] = []) -> None:
        "Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"
        a = list(a)
        if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):
            a = sorted(a)
        self._build(a)

    def __iter__(self) -> Iterator[T]:
        for i in self.a:
            for j in i: yield j

    def __reversed__(self) -> Iterator[T]:
        for i in reversed(self.a):
            for j in reversed(i): yield j
    
    def __len__(self) -> int:
        return self.size
    
    def __repr__(self) -> str:
        return "SortedMultiset" + str(self.a)
    
    def __str__(self) -> str:
        s = str(list(self))
        return "{" + s[1 : len(s) - 1] + "}"

    def _find_bucket(self, x: T) -> List[T]:
        "Find the bucket which should contain x. self must not be empty."
        for a in self.a:
            if x <= a[-1]: return a
        return a

    def __contains__(self, x: T) -> bool:
        if self.size == 0: return False
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        return i != len(a) and a[i] == x

    def count(self, x: T) -> int:
        "Count the number of x."
        return self.index_right(x) - self.index(x)

    def add(self, x: T) -> None:
        "Add an element. / O(√N)"
        if self.size == 0:
            self.a = [[x]]
            self.size = 1
            return
        a = self._find_bucket(x)
        insort(a, x)
        self.size += 1
        if len(a) > len(self.a) * self.REBUILD_RATIO:
            self._build()

    def discard(self, x: T) -> bool:
        "Remove an element and return True if removed. / O(√N)"
        if self.size == 0: return False
        a = self._find_bucket(x)
        i = bisect_left(a, x)
        if i == len(a) or a[i] != x: return False
        a.pop(i)
        self.size -= 1
        if len(a) == 0: self._build()
        return True

    def lt(self, x: T) -> Union[T, None]:
        "Find the largest element < x, or None if it doesn't exist."
        for a in reversed(self.a):
            if a[0] < x:
                return a[bisect_left(a, x) - 1]

    def le(self, x: T) -> Union[T, None]:
        "Find the largest element <= x, or None if it doesn't exist."
        for a in reversed(self.a):
            if a[0] <= x:
                return a[bisect_right(a, x) - 1]

    def gt(self, x: T) -> Union[T, None]:
        "Find the smallest element > x, or None if it doesn't exist."
        for a in self.a:
            if a[-1] > x:
                return a[bisect_right(a, x)]

    def ge(self, x: T) -> Union[T, None]:
        "Find the smallest element >= x, or None if it doesn't exist."
        for a in self.a:
            if a[-1] >= x:
                return a[bisect_left(a, x)]
    
    def __getitem__(self, x: int) -> T:
        "Return the x-th element, or IndexError if it doesn't exist."
        if x < 0: x += self.size
        if x < 0: raise IndexError
        for a in self.a:
            if x < len(a): return a[x]
            x -= len(a)
        raise IndexError

    def index(self, x: T) -> int:
        "Count the number of elements < x."
        ans = 0
        for a in self.a:
            if a[-1] >= x:
                return ans + bisect_left(a, x)
            ans += len(a)
        return ans

    def index_right(self, x: T) -> int:
        "Count the number of elements <= x."
        ans = 0
        for a in self.a:
            if a[-1] > x:
                return ans + bisect_right(a, x)
            ans += len(a)
        return ans
class SegmentTree:
    def __init__(self, v,marge,default):
        self.default = default
        self.marge = marge
        self.lastnode = 1
        self.h = 1
        while self.lastnode < len(v):
            self.lastnode*=2
            self.h += 1
        #1-indexedで作成する
        self.array = [self.default] *(2*self.lastnode)
        self.lazy = [0] *(2*self.lastnode)
        for i in range(len(v)):
            self.array[self.lastnode+i] = v[i]
        for i in range(self.lastnode-1,-1,-1):
            self.array[i] = self.marge(self.array[2*i],self.array[2*i+1])
    def propagate(self,i):
        if self.lazy[i] != 0:
            v = self.lazy[i] #下に伝播させるやつ
            if i < self.lastnode:
                self.lazy[i] = 0
                self.lazy[2*i]+= v
                self.lazy[2*i+1] += v
                self.array[2*i] += v
                self.array[2*i+1] += v
            self.lazy[i] = 0
    def eval(self,L,R):
        L+=self.lastnode
        R+=self.lastnode
        L0 = L // (L & -L)  # 奇数になるまで L を 2 で割ったもの
        R0 = R // (R & -R)  # 奇数になるまで R を 2 で割ったもの
        H = L0.bit_length() - 1
        for n in range(H, -1, -1):
            self.propagate(L0>>n)
        H = R0.bit_length() - 1
        for n in range(H, -1, -1):
            self.propagate(R0>>n)
        
    def recalc(self,L,R):
        L+=self.lastnode
        R+=self.lastnode
        L0 = L // (L & -L)  # 奇数になるまで L を 2 で割ったもの
        R0 = R // (R & -R)  # 奇数になるまで R を 2 で割ったもの
        while L0 > 1:
            L0 >>= 1
            self.array[L0] = self.marge(self.array[2*L0],self.array[2*L0+1])
        while R0 > 1:
            R0 >>= 1
            self.array[R0] = self.marge(self.array[2*R0],self.array[2*R0+1])
    def add(self,q_left , q_right,val):
        self.eval(q_left , q_right)
        L,R = q_left, q_right
        q_left += self.lastnode
        q_right += self.lastnode
        while q_left < q_right:
            if q_left&1:
                self.array[q_left] += val
                self.lazy[q_left] += val
                q_left += 1
            if q_right&1:
                q_right -= 1
                self.array[q_right] +=val
                self.lazy[q_right] += val
            q_left >>= 1
            q_right>>= 1
        self.recalc(L,R)
    def query(self,q_left,q_right):
        self.eval(q_left , q_right)
        q_left += self.lastnode
        q_right += self.lastnode
        
        lres,rres = self.default,self.default
        while q_left < q_right:
            if q_left&1:
                lres = self.marge(lres,self.array[q_left])
                q_left += 1
            if q_right&1:
                q_right -= 1
                rres = self.marge(self.array[q_right],rres)
            q_left >>= 1
            q_right>>= 1
        return self.marge(lres,rres)
 
from collections import defaultdict
N = int(input())

enter = defaultdict(SortedMultiset)
info = []
times = set()
for i in range(N):
  X,L,R = input().split()
  L = int(L)
  R = int(R)
  info.append((X,L,R))
  times.add(L)
  times.add(R)
Q = int(input())
querys = []
for i in range(Q):
  q,*arg = input().split()
  q = int(q)
  querys.append((q,arg))
  if q == 1:
    times.add(int(arg[1]))
  elif q == 2:
    times.add(int(arg[0]))
  else:
    times.add(int(arg[1]))
    times.add(int(arg[2]))
compttmp = sorted(list(times))
compt = {compttmp[i]:i for i in range(len(compttmp))}
st = SegmentTree([0]*len(compt),lambda x,y:x+y,0)
for X,L,R in info:
  enter[X].add((L,R))
  st.add(compt[L],compt[R]+1,1)
for q,arg in querys:
  if q == 1:
    x,t = arg
    t = int(t)
    z = enter[x].lt((t,10**18))
    if z is None:
      print("No")
    else:
      l,r = z
      if l <= t <= r:
        print("Yes")
      else:
        print("No")
  elif q == 2:
    t = int(arg[0])
    print(st.query(compt[t],compt[t]+1))
  else:
    x,l,r = arg
    l = int(l)
    r = int(r)
    enter[x].add((l,r))    
    st.add(compt[l],compt[r]+1,1)
0